棒棒糖圖的IC-著色和IC-指數(shù)

張楚文，王力工

（西北工業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)系，陜西 西安710072）

1 引言及定義

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

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

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

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

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

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

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］當(dāng)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-指數(shù)的上下界，如下：

7）［5］

8）［5］

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

10）［12-13］設(shè)n(n≥2 )個整數(shù)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-指數(shù)的一個上界。并用計算機編程得到m=3，4，5幾類棒棒糖圖Bm，n的IC-著色及IC-指數(shù)。即當(dāng)m=3，n=1，2，…6 時，有M（B3，n）=5n+2；當(dāng)m=4，n=1，2，…5 時，有M（B4，1）=13，M（B4，3）M（B4，4）=34，M（B4，5）=40；當(dāng)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-指數(shù)的幾個結(jié)果

定理1設(shè)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中所有連通子圖的總數(shù)，用Ni表示由i個頂點構(gòu)成的連通子圖總數(shù)。如果存在單射f為圖Bm,n的一個IC-著色，那么只有當(dāng)任意兩個連通子圖Hi和Hj，滿足f(Hi)≠f(Hj)時，才有M(Bm,n)=R(Bm,n)，否則，M(Bm,n)＜R(Bm,n)。顯然R(Bm,n)是的M(Bm,n)一個上界。下面只要推導(dǎo)R(Bm,n)公式即可。

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

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

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

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

綜上所述

所以上界得證。

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

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

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

2）當(dāng)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）當(dāng)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-指數(shù)和極大IC-著色Fig.2 The IC-indices and maximal IC-colorings of several lollipop graphs Bm,n

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

1）當(dāng)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個點構(gòu)成的連通子圖的IC-著色

2）當(dāng)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個點構(gòu)成的連通子圖的IC-著色

以上數(shù)遍歷［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）當(dāng)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個點構(gòu)成的連通子圖的IC-著色：

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

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

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

3 算法

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

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

算法步驟：

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

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

在圈Cm中，循環(huán)求和，求出

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

在交界區(qū)域，求出

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

第4步 從第3步中得到符合條件的結(jié)果中，篩選出最大IC-指數(shù)和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著色的認(rèn)識差分調(diào)頻系統(tǒng)多址原理[J].武漢大學(xué)學(xué)報:理學(xué)版,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] 周娟,謝承旺,徐保根,等.關(guān)于圈Cn的IC-著色和IC-指數(shù)[J].華東交通大學(xué)學(xué)報,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].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2012,28(2):201-212.

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

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

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