章鱼图的IC-着色和IC-指数

杨杨，王力工

（西北工业大学理学院应用数学系，陕西西安710072）

章鱼图的IC-着色和IC-指数

杨杨，王力工

（西北工业大学理学院应用数学系，陕西西安710072）

章鱼图H（Cm，n）是指由圈Cm的一个顶点与星图STn=K1，n的中心重迭得到的图，研究了章鱼图H（Cm，n）的IC-着色问题，通过分类讨论的方法，分别得到了当m=3，4，5，n≥1时章鱼图H（Cm，n）的极大IC-着色和它们相应的IC-指数，并提出章鱼图H（Cm，n）一个上界猜想。

IC-着色；IC-指数；章鱼图

本文所指的图均为无向简单图，文中未说明的符号和术语可参考文献［1］。

设图G=(V,E)是一个连通图，对于图G的一个着色f:V(G)→ℕ和G的一个子图H，定义f(H)=∑v∈V(H)f(v)，特别的将f(G)记作S(f)。如果对于任意整数k∈{1,2,3,…,f(G)}≜[1,f(G)]存在G的一个连通子图H，使得f(H)=k,则称f为图G的一个IC-着色。并定义M(G)=max{f(G) f为图G的一个IC-着色}为图G的IC-指数，并且称适合f(G)=M(G)的IC-着色f为图G的一个极大IC-着色。

图的IC-着色问题来源自数论中邮票问题［2-4］，自从提出以来，得到了广泛的研究：1995年，Penrice在文献［4］得到结论：

1）M(Kn)=2n。

2）当n≥2时，M(K1,n)=2n+n。

3）当3≤n≤9，n≠7时，M(Cn)=n(n-1)+1。

2005年，Salehi等人在文献［5］正式提出IC-着色和IC-指数的概念，并得到结论：当n≥2时，M(K2,n)=3∙2n+1。2006年，徐宝根在文献［6］得到结论：设整数n≥2且b1≥b2≥…≥bn≥2则M(ST(n;b1,b2,…,bn))≥2b1+∑ni=-11(bi+1-1)bin，2008年，Shiue和Fu在文献［7］得到结论：当2≤m≤n时，M(Km,n)=3∙2m+n-2-2m-2+2。2011年，陈剑峰在文献［8］与［9］当中分别得到了笛卡尔积图Pm×Pn和星的细分图的IC-指数的一个下界。2012年，周娟等在文献［10］得到结论当n=10,12,14时，M(Cn)=n(n-1)+1。2012年，陈剑峰等在文献［11］和文献［12］研究了双星图的IC-着色，得到了：对于双星图DS(m,n)(2≤m≤n)的IC-着色，设f是G=DS(m,n)的一个极大IC-着色，则当f(v1)=1时，有M(G)=(2m-1+1)(2n-1+1)，而且f是唯一的，并由这个结论得到了双星图的IC-指数为M(DS(m,n))=(2m-1+1)(2n-1+1)。

章鱼图H（Cm，n）是指由圈Cm的一个顶点与星图STn=K1，n的中心重叠得到的图，本文研究了章鱼图H（Cm，n）的IC-着色问题，分别得到了当m=3，4，5，n≥1时章鱼图H（Cm，n）的极大IC-着色和它们的IC-指数，并给出章鱼图H（Cm，n）IC-指数的一个上界猜想。

对于章鱼图H（Cm，n），如图1。圈的顶点集设为V(Cm)={ui|1≤i≤m}，星图的顶点集设为V(STn)= {vj|1≤j≤n}，记星图STn的中心为u1=v。

定理1当m=3，n≥1时，章鱼图G=H（Cm，n）的IC-指数满足

证明当m=3,n≥1时，章鱼图G=H(Cm,n)的一个着色记为f，其中f(u1)=5，f(u2)=1，f(u3)=2，f(vj)=2j+1(j=1,2,…,n)，下面证明f是章鱼图G=H(Cm,n)的一个IC-着色。

图1 章鱼图H(Cm,n)Fig.1 Octopus GraphH(Cm,n)

当k∈[1,5]时，若k=1，有f(u2)=1；若k=2，有f(u3)=2；若k=3，有f(u2)+f(u3)=3；若k=4，有f(v1)=4；若k=5，有f(u1)=5；当k∈[6,2n+1+4]时，记u1=v-1,u2=v0，考虑k-5的展开式：，对k∈[6,2n+2+4]，存在由点导出的连通子图Hk，使得f(Hk)=k，综上可知f是章鱼图G=H(Cm,n)的IC-着色，从而得到

定理2当m=3,n≥1时，章鱼图G=H(Cm,n)的IC-指数为

证明当m=3,n≥1时，定理3.1已证得M(G)≥S(f)=[m(m-1)/2+1](2n+1)，下面只需证M(G)≤[m(m-1)/2+1](2n+1)=2n+2+4。设章鱼图G=H(Cm,n)=H(C3,n)的IC-指数为M，对k=1,2,3,…，依次寻找图G的连通子图Hk，使得f(Hk)=M-k，在着色的过程中，目标是选择使M最大的方案，下面分步骤进行着色。

步骤1：当k=1时，为使连通子图H1存在，要对章鱼图H(C3,n)上的点着色1，着色为1的点可以为u2或v1。

情况1：当f(u2)=1，存在连通子图H1=G{u2}，使得f(H1)=M-1。

情况2：当f(v1)=1，存在连通子图H1=G{v1}，使得f(H1)=M-1。

步骤2：当k=2时，为使连通子图H2存在，要对章鱼图H(C3,n)上的点着色1或2，在步骤1的情况1下，着色的点可以为u3或v1，在步骤1的情况2下，着色的点可以为u2或v2。为了使得M尽可能大，此步骤中的以下4种情形为最优方案。

情况1：当f(u2)=1，f(u3)=2，存在连通子图H2=G{u3}，使得f(H2)=M-2，存在连通子图H3=G{u2,u3}，使得f(H3)=M-3。

情况2：当f(u2)=1，f(v1)=2，存在连通子图H2=G{v1}，使得f(H2)=M-2，存在连通子图H3=G{u2,v1}，使得f(H3)=M-3。

情况3：当f(u2)=2，f(v1)=1，存在连通子图H2=G{u2}，使得f(H2)=M-2，存在连通子图H3=G{u2,v1}，使得f(H3)=M-3。

情况4：当f(v1)=1，f(v2)=2，存在连通子图H2=G{v2}，使得f(H2)=M-2，存在连通子图H3=G{v1,v2}，使得f(H3)=M-3。

步骤3：显然在步骤2的4种情形下都存在图G的连通子图H3，使得f(H3)=M-3。当k=4时，根据步骤1和步骤2的着色规则继续着色，得到以下7种情况。

情况1：当f(u2)=1，f(u3)=2，f(v1)=4，存在连通子图H4=G{v1}，使得f(H4)=M-4；存在连通子图H5=G{u2,v1}，使得f(H5)=M-5；存在连通子图H6=G{u3,v1}，使得f(H6)=M-6；存在连通子图H7=G{u2,u3,v1}，使得f(H7)=M-7。以下情况同步骤3中的情况1可得，存在连通子图Hk，使得f(Hk)=M-k，k=4,5,6,7。

情况2：当f(u2)=1，f(u3)=4，f(v1)=2。

情况3：当f(u2)=1，f(v1)=2，f(v2)=2。

情况4：当f(u2)=2，f(u3)=4，f(v1)=1。

情况5：当f(u2)=2，f(v1)=1，f(v2)=4。

情况6：当f(u2)=4，f(v1)=1，f(v2)=2。

情况7：当f(v1)=1，f(v2)=2，f(v3)=4。

继续进行着色时，不失一般性，以步骤三的情况1为例，下面依次对点v2,v3,v4,…进行着色。考虑k=8时，为使连通子图H8存在，需满足f(v2)+l=8，其中l∈{0,1,2,3,4,5,6,7}，易知1≤f(v2)≤8，为保证着色极大，则f(v2)=8，同理可得，为使得f(Hk)=M-k,k=1,2,3,…的连通子图Hk存在，且保证着色极大，易证除中心v外，余下的点的着色一定为16,32,64,…,2n-1，此时已对章鱼图中的n个点完成着色。

当对章鱼图中的n个点（除中心v外）的着色为1,2,4,…,2n-1时，存在一种特殊情形，仅对星图顶点的着色，着色为f(vj)=2j-1，j=1,2,3,…,n，此时可以找到连通子图Hk，使得cj=0.1，连通子图为，从而当k=1,2,3,…,2n-1时，可以找到连通子图Hk，使得f(Hk)=M-k，下面分2种情形继续着色。

情形1：当f(u1)=1时，H′=G{v,v1,v2,…,vn}=G[u2,u3]为连通子图且f(H)=M-2n。为使数M-(2n+1)对应一个连通子图，应有f(u2)+l=2n+1，l∈{0,1,2,3,…,2n}，记u2的着色为α，则α≤2n+1，此时M-k都对应一个连通子图，其中k=1,2,3,…,2n+α，再考虑数M-(2n+α+1)所对应的连通子图，同理有f(u3)≤2n+α+1。当f(ui)(i=2,3)都取得最大值时，依次检验数i=1,2,…,2n+2+3，都有连通子图与之对应，此时，极大着色为S(f1)=2n+2+3。

情形2：当f(u1)≠1时，为使数M-2n对应一个连通子图，应有f(u2)+l=2n，l∈{0,1,2,3,…,2n-1}，记u2的着色为α，则α≤2n，此时则M-k都对应一个连通子图，其中k=1,2,3,…,2n-1+α，再考虑数M-(2n+α)所对应的连通子图，同理有f(u3)≤2n+α。当f(ui)(i=2,3)都取得最大值时，依次检验数i=1,2,3,…，发现当i=3时，无连通子图与之对应，从而应有f(u1)≤3，此时，极大着色为S(f2)=2n+2+2。

当对章鱼图中的n个点（除中心v外）的着色为1,2,4,…,2n-1时，除去上述仅对章鱼图中的星图着色的情况外，继续着色，易证，余下点的着色必为2n,2n+1,…；此时，除章鱼图的中心v之外，其它点的着色都已经确定。

下面以步骤3中的情况1，情况2的着色为例进行分析。

对于步骤3中的情况1，继续着色，着色为f(u2)=1，f(u3)=2，f(vj)=2j+1，j=1,2,…,n，依次检验i=1,2,3,…，发现当i=5时，无连通子图与之对应，故对中心v着色使得f(v)+l=5，l∈{0,1,2,4}，易知1≤f(v)≤5，当f(v)取得最大值时，依次检验i=1,2,3,…,2n+2+4，都有连通子图与之对应，此时，极大着色为S(f3)=2n+2+4。

对于步骤3中的情况2，继续着色，着色为f(u2)=1，f(u3)=4，f(v1)=2，f(vj)=2j+1，j=2,3,…,n，依次检验i=1,2,3,…，发现当i=3时，无连通子图与之对应，故对中心v着色使得f(v)+l=3，l∈{0,1,2}，易知1≤f(v)≤3，当f(v)取得最大值时，依次检验i=1,2,3,…,2n+2+2，都有连通子图与之对应，此时，极大着色为S(f4)=2n+2+2。

通过对步骤3的2种着色情况的分析，推广到所有情况，当所有点（除中心v外）的着色确定后，依次检验i=1,2,3,…，当i=3时，发现除步骤3的情况1之外，无连通子图与之对应，故对中心v着色使得f(v)+l=3，l∈{0,1,2}，易知1≤f(v)≤3，当f(v)取得最大值时，依次检验i=1,2,3,…,2n+2+2，都有连通子图与之对应，此时，极大着色为S(f)=2n+2+2。

综合以上所有情况可知，章鱼图H（Cm，n）=H（C3，n）的着色满足f(G)≤S(f1)=2n+2+4，结合定理3.1可知当m=3,n≥1时，章鱼图G=H（Cm，n）的IC-指数为

例1当m=3,n≥1时，章鱼图H（Cm，n）=H（C3，n）的极大IC-着色见图2。

定理3当m=4，n≥1时，章鱼图H（Cm，n）的IC-指数为

图2 章鱼图H（C3，n）的极大IC-着色Fig.2 Maximal IC-coloring of H（C3，n）

证明当m=4，n≥1时，记章鱼图的着色为f，章鱼图H（Cm，n）=H（C4，n）的着色为f(u1)=8， f(u2)=1，f(u3)=3，f(u4)=2，f(vj)=7∙2j-1(j=1,2,…,m)，同定理3.1的证明可得，f是章鱼图G=H（Cm，n）的IC-着色，从而得到当m=3,4,n≥1时，M(G)≥S(f)=[m(m-1)/2+1](2n+1)=7∙2n+7。

下面证明M(G)≤[m(m-1)/2+1](2n+1)=7∙2n+7，设章鱼图G=H(Cm,n)=H(C4,n)的IC-指数为M，对k=1,2,3,…，依次寻找连通子图Hk，使得f(Hk)=M-k，下面分步骤进行着色（由于情况太多，在此不一一列举），仿照定理3.2的证明，可得当m=3,4,n≥1时，M(G)≤S(f)=[m(m-1)/2+1](2n+1)=7∙2n+7，从而章鱼图G=H(Cm,n)=H(C4,n)的IC-指数为M(G)=[m(m-1)/2+1](2n+1)=7∙2n+7。

例2当m=4,n≥1时，章鱼图H(Cm,n)=H(C4,n)的极大IC-着色见图3。

定理4当m=5,n≥1时，章鱼图G=H(Cm,n)的IC-指数为

证明当m=5,n≥1时，记章鱼图的着色为f，章鱼图G=H(Cm,n)=H(C5,n)的着色为f(u1)=5，f(u2)=1，f(u3)=3，f(u4)=5∙2n+5，f(u5)=2，f(vj)=5∙2j-1(j=1,2,…,m)，参照定理1和定理2的证明，同理可证得，这一着色是章鱼图G=H(Cm,n)的一种极大IC-着色，IC-指数为M(G)=11+10×2n。

例3当m=5,n≥1时，章鱼图H(Cm,n)=H(C5,n)的极大IC-着色见图4。

图3 章鱼图H（C4，n）的极大IC-着色Fig.3 Maximal IC-coloring of H（C4，n）

图4 章鱼图H(C5,n)的极大IC-着色Fig.4 Maximal IC-coloring of Octopus GraphH(C5,n)

猜想当m≥3,n≥1时，章鱼图H(Cm,n)的IC-指数的上界为

[1]SALEHI E,SIN MIN LEE,KHATIRINEJAD M S.IC-colorings and IC-indices of graphs[J].Discrete Mathematics,2005,299(8): 297-310.

[2]ALTER R,BRNETT J A.A postage stamp problem[J].The American Mathematical Monthly,1980,87(3):206-210.

[3]程卓,王殊.基于IC着色的认知差分跳频系统多址原理[J].武汉大学学报:理学版,2010,56(4):478-482.

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

[6]徐宝根.关于连通图的IC-着色[J].华东交通大学学报,2006,23(1):134-136.

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

[8]陈剑峰.笛卡尔积图Pm×Pn的IC-着色[J].莆田学院学报,2011,18(2):13-15.

[9]陈剑峰.星的细分图的IC-着色[J].莆田学院学报,2012,19(2):11-13.

[10]周娟,谢承旺,徐宝根.关于圈Cn的IC-着色和IC-指数[J].华东交通大学学报,2012,29(4):64-68.

[11]陈剑峰,杨大庆.双星图的IC-着色[J].纯粹数学与应用数学,2012,28(2):201-212.

[12]陈剑峰,杨大庆.双星图的IC-指数[J].数学的实践与认识,2013,43(7):132-140.

IC-coloring and IC-index of Octopus Graphs

Yang Yang,Wang Ligong
(Department of Applied Mathematics,School of Science,Northwestern Polytechnical University,Xi'an 710072,China)

The octopus graphH(Cm,n)is formed by identifying a vertex of the cycleCmand the center of a starSTn=K1,n.In this paper,the problem of IC-colorings on the octopus graph is studied.Whenm=3,4,5,n≥1,IC-indices andmaximal IC-colorings of the octopus graphH(Cm,n)are obtained respectively.A conjecture for the up⁃per bound of the IC-index of the octopus graph is proposed.

IC-coloring;IC-index;octopus graph

O157.5

A

2014-01-10

国家自然科学基金（11171273）；国家级大学生创新创业训练计划项目资助（201310699069）

杨杨（1990—），男，硕士研究生，研究方向为图论；王力工（1968—），男，教授，博士生导师，研究方向为图论及应用。

1005-0523（2014）04-0077-05