棒棒糖圖的IC-著色和IC-指數

張楚文，王力工

（西北工業大學理學院應用數學系，陜西 西安710072）

1 引言及定義

圖的IC-著色問題有著很強的實際背景，它源自數論中的郵票問題［1-3］，近年來在無線電網絡通信中有所應用，例如程卓等人［4］提出來基于IC-著色和干擾溫度模型的差分調頻系統多址原理，用IC-著色與干擾溫度理論控制網內用戶的發射行為，使之達到區分預期信號和干擾信號的目的。Salehi E等人［5］于2005年引入了圖的IC-著色的概念并得到了一些結果。

定義1［6］設G=(V,E)是一個圖，N是正整數集。V={v1,v2,...,vn}，f是定義在V上的，取值在N的函數，若對于任意兩個相連的點vi和vj，f(vi)不等于f(vj)，則稱f是G的一個著色。

定義2［5］設圖G是一個連通圖，對于圖G的一個著色f和圖G的一個H子圖，則記f(H)=∑f(v),v∈V(H)，特別的將f(G)記作S(f)。如果對于任意整數k∈{1 ,2,3,…,f(G)},存在G的一個連通子圖H，使得f(H)=k，則稱f為圖G的一個IC-著色。并定義M(G)=max{f(G)}為圖G的IC-指數，并且稱適合f(G)=M(G)的IC-著色f為圖G的一個極大IC-著色。

由定義易得，一個圖G存在IC-著色的必要條件是G為連通圖。

定義3棒棒糖圖Bm,n是由圈Cm上的任一個頂點和路Pn的一個1度頂點重合而得到n+m-1 階的連通圖。

一般地說，確定一個圖的IC-指數是困難的，由文獻［5，7-13］已知一些圖的IC-指數：完全圖Kn，星K1,n，完全二部圖Km,n，圈Cn，路Pn，Kn-e（表示減掉一條邊的n階完全圖），雙星圖DS(m,n)（由兩個星圖K1,m和K1,n的中心連一條新邊得到的圖），其結果如下：

1）［5］M(Kn)=2n-1；Kn的最大著色：(1,2,4,8,...,2n-1)。

2）［7］M(K3-e)=6；M(Kn-e)=2n-3，n≥4。

3）［8］當n∈{3,4,5,6,8,9,10,12,14}時，則M(Cn)=n(n-1) +1。

4）［5］M(K1,n)=2n+2,2 ≤n。

5）［9］M(Km;n)=3×2m+n-2-2m-2+2，2 ≤m≤n。

Km,n的最大著色f，Km,n的頂點二劃分(X,Y)，其中X={x1,x2,...,xm}，Y={y1,y2,...,yn}。

6）［10-11］M(DS(m,n))=( 2m-1+1)( 2n-1+1),2 ≤m≤n。

對于其他類型的某些圖的IC-指數的上下界，如下：

7）［5］

8）［5］

9）［12-13］對任意連通圖G和H，均有M(G+H)＞(M(G)+1)(M(H)+1) -1。

10）［12-13］設n(n≥2 )個整數bi(i=1,2,...,n)滿足b1≥b2≥b3≥...≥bn≥2，則有M(ST(n;b1,b2,...,bn))≥2b1+∑(bi+1-1)bin,1 ≤i≤n。

研究棒棒糖圖Bm，n的IC-著色問題，得到它的IC-指數的一個上界。并用計算機編程得到m=3，4，5幾類棒棒糖圖Bm，n的IC-著色及IC-指數。即當m=3，n=1，2，…6 時，有M（B3，n）=5n+2；當m=4，n=1，2，…5 時，有M（B4，1）=13，M（B4，3）M（B4，4）=34，M（B4，5）=40；當m=5，n=1，2，3，4時，有M（B5，1）=21，M（B5，2）=31，M（B5，3）=39，M（B5，4）=48。最后猜想：對于棒棒糖圖B3，n，則有M（B3，n）5n+2。

2 棒棒糖圖IC-著色和IC-指數的幾個結果

定理1設Bm,n是一個具有n+m-1 個頂點的棒棒糖圖， 圖1所示，其中{v1,v2,...,vm}?V(Cm)?V(Bm,n),{w1=v1,w2,...,wn}?V(Pm)?V(Bm,n)，則

圖1 棒棒糖圖Bm,nFig.1 Lollipop graph Bm,n

證明：用R(Bm,n)表示棒棒糖圖Bm,n中所有連通子圖的總數，用Ni表示由i個頂點構成的連通子圖總數。如果存在單射f為圖Bm,n的一個IC-著色，那么只有當任意兩個連通子圖Hi和Hj，滿足f(Hi)≠f(Hj)時，才有M(Bm,n)=R(Bm,n)，否則，M(Bm,n)＜R(Bm,n)。顯然R(Bm,n)是的M(Bm,n)一個上界。下面只要推導R(Bm,n)公式即可。

R(Bm,n)的計算分成3個部分：

1）計算棒棒糖圖Bm,n中圈Cm的連通子圖總數，其值用R1表示。 因為在圈Cm中N1,N2,…,Nm-1=m，Nm=1，所以

2）計算棒棒糖圖Bm,n中路Pn-1的連通子圖總數，其值用R2表示。因為在路Pn-1中N1=n-1,N2=n-2,…,Nn-1=1，所以

3）計算棒棒糖圖Bm,n中圈Cm和路Pn交界的連通子圖總數，其值用R3表示，在圈中包含第一個頂點的連通子圖個數為，分別和路Pn-1的各個頂點相連，所以

綜上所述

所以上界得證。

計算機、軟件以及數據庫等是虛擬教程，那么實體化的課程呢？沈陽工學院對部分專業課程進行了工作過程系統化教學模式的探索，如水利工程管理、計算機科學與技術、工程材料、水利工程概預算、施工組織與造價等課程。在不改變課程的教學大綱和原有教學計劃的前提下，將授課內容按工作過程系統化模式進行了重新構建、整合。通過教學實踐，收到了很好的效果。授課內容及形式更貼近工作實際，大大激發學生的學習熱情，一定程度上提升了學生處理工程問題的能力。

定理2在棒棒糖圖Bm,n中，圈Cm的頂點集V(Cm)={v1,v2,...,vm}，其中頂點vi的著色為f(vi)，路Pn的頂點集V(Pm)={w1,w2,...,wm}，其中頂點wi的著色為f(wi)，有以下結論。

1）當m=3,n=1,2,…6 時，有M(B3,n)=5n+2。

2）當m=4，n=1,2,…5 時，有M(B4,1)=13,M(B4,2)=21,M(B4,3)=26,M(B4,4)=34,M(B4,5)=40。

3）當m=5，n=1,2,3,4 時，有M(B5,1)=21,M(B5,2)=31,M(B5,3)=39,M(B5,4)=48。

具體著色如圖2所示。

圖2 一些棒棒糖圖Bm,n 的IC-指數和極大IC-著色Fig.2 The IC-indices and maximal IC-colorings of several lollipop graphs Bm,n

證明：分別對m=3,4,5 中的一種情況進行證明，同理可證其他情況。

1）當m=3,n=6，{f(v1),f(v2),f(v3)}={9,1,3},{f(w1),f(w2),...,f(w6)}={9,4,7,2,5,1}，求證

下面給出分別由1，2，…，8個點構成的連通子圖的IC-著色

2）當m=4,n=5，{f(v1),f(v2),...,f(v4)}={8,2,7,4},{f(w1),f(w2),...,f(w5)}={8,3,10,5,1}，求證

下面給出分別由1，2，…，8個點構成的連通子圖的IC-著色

以上數遍歷［1，40］，所以f(B4,5)=40 ，即對任意j(1 ≤j≤f(B4,5)=40 )，都存在圖B4,5的連通子圖H使得j=f(H)。又因為計算機驗證得出不存在f(B4,5)=41的IC-著色，所以

3）當m=5,n=4，{f(v1),f(v2),...,f(v5)}={12,2,5,1,3},{f(w1),f(w2),...,f(w4)}={12,12,3,10}，求證

下面給出分別由1，2，…，8個點構成的連通子圖的IC-著色：

以上數遍歷［1，48］，所以f(B5,4)=48 ，即對任意j(1 ≤j≤f(B5,4)=48) ，都存在圖B5,4的連通子圖H使得j=f(H)。又因為計算機驗證得出不存在f(B5,4)=49 的IC-著色，所以

結論分析：借助計算機編程和理論分析等方法，得到了定理1、2，即得到棒棒糖圖Bm,n的IC-指數的一個上界和一些階數較小的棒棒糖圖Bm,n的IC-指數。由定理2 知道，當m=3,n=1,2,…,6 時，有M(B3,n)=5n+2。而對于m=4 和m=5 的棒棒糖圖Bm,n，其IC-著色M(B4,n),M(B5,n)關于n的函數關系并不顯著。因此我們猜想：

猜想：對于任意正整數n，則有M(B3,n)=5n+2。

3 算法

棒棒糖圖Bm,n是由圈Cm和路Pn共同組成，而圈和路的IC-指數和著色都沒有發現明確規律，所以要確定棒棒糖圖Bm,n的IC-指數是困難的。因此，我們采用計算機編程來求解棒棒糖圖Bm,n的IC-指數與相應IC- 著色，也就是要找到n+m-1 個正整數x1,x2,...,xm;y2,y3,...,yn，其中xi=f(vi),yi=f(wi) ，，使得其滿足以下幾個條件：

1）存1性，至少存在一點xi=1或yi=1。

算法步驟：

第1步 枚舉n+m-1個正整數x1,x2,...,xm;y2,y3,...,yn，并保證其滿足條件1）2）。

第2步 分成三部分計算所有的著色：

在圈Cm中，循環求和，求出

在路Pn中，單向求和，求出

在交界區域，求出

第3步 若第2步中所求結果滿足條件3），則保留x1,x2,...,xm;y2,y3,...,yn的取值并記下此時的IC-指數

第4步 從第3步中得到符合條件的結果中，篩選出最大IC-指數和IC-著色。

[1] ALTER R,BERNTT J A.A postage stamp problem[J].Amer Math Monthly,1980,87:206-210.

[2] HEIMER R L,LANGNBACH H.The Stamp Problem[J].J Recreational Math,1974,7:235-250.

[3] LUNON W F.A Postage stamp problem[J].Comput J,1969,12:377-380.

[4] 程卓,王殊,屈曉旭,等.基于IC著色的認識差分調頻系統多址原理[J].武漢大學學報:理學版,2010,56(4):1-7.

[5] SALEHI E,LEE S,KHATIRINEjAD M.IC-colorings and IC-indices of graphs[J].Discrete Mathematics, 2005,299:297-310.

[6] BONDY J A,MURTY U S R.Graph theory with applications[M].Amsterdam:Elsevier Science Publishing Co.Inc,1976:156-160.

[7] PENRICE S G.Some new graph labeling problems:A preliminary report[J].DIMACS Technical Reports,1995,95(7):1-9.

[8] 周娟,謝承旺,徐保根,等.關于圈Cn的IC-著色和IC-指數[J].華東交通大學學報,2012,29(4):64-68.

[9] SHIUE CL,FU H L.The IC-indices of complete bipartite graphs[J].The Electronic Journal of Combinatorics,2008,15(43):1-13.

[10] 陳劍峰,楊大慶.雙星圖的IC-著色[J].純粹數學與應用數學,2012,28(2):201-212.

[11] 陳劍峰,楊大慶.雙星圖的IC-指數[J].數學的實踐與認識,2013,43(7):132-140.

[12] 徐保根.關于連通圖的IC-著色[J].華東交通大學學報,2006,23(1):134-136.

[13] 徐保根.圖的控制理論[M].北京:科學出版社,2006:33-37.