Mycielski图的一般邻点可区别全色数

2017-01-13王继顺

海南大学学报（自然科学版） 2016年4期

关键词：邻点全色区别

王继顺

(连云港师范高等专科学校数学与信息工程学院，江苏连云港 222006)

Mycielski图的一般邻点可区别全色数

王继顺

(连云港师范高等专科学校数学与信息工程学院，江苏连云港 222006)

Mycielski图；一般邻点可区别全染色；一般邻点可区别全色数

由信息科学中的电信通讯站的频率分配问题、计算机科学中的网络结构设计区分问题所引出的点可区别边染色[1-3]，邻点可区别边染色[4-5]，邻点可区别全染色[6]等具有一定的理论价值和实际意义，逐渐成为图论工作者研究的重要课题[7-10]. 为拓展图染色理论的应用领域，文献[11]进一步提出了一般邻点可区别边染色概念，文献[12-13]提出图的一般邻点可区别全染色的新染色概念. 由于其同样是十分困难的问题，至今文献甚少. 文献[14]根据路、圈、扇、轮等图的结构性质，确定了其一般邻点可区别的全色数．

1 相关定义与猜想

定义1[6]设G(V，E)是简单连通图，k是正整数，f是V∪E(G)到{1，2，…k}的映射，若f满足

关于图的一般邻点可区别全色数，有2个猜想.

猜想2[12-13]设G(V，E)是有n个顶点的简单图，且Δ(G)≥4，则χgat≤Δ(G)+1.

Mycielski图是图论中一种重要的图，也是实际应用中经常遇到的一种网络.文献[7,15-17]研究了Mycielski图的相关染色，笔者从Mycielski图的构造特点出发，运用构造法、概率法及色调整技术研究了路、圈、扇、星、轮、完全图和完全二部图的一般邻点可区别全染色问题，得到其一般邻点可区别全色数.

文中所涉及的图都是简单连通有限图，未给出的术语与记号参见文献[18].

2 主要结论与证明

引理1 设G(V，E)图为简单图，

1) 如果E(G)≠Ø，则χgat(G)≥2；

2) 如果G(V,E)含K3，则χgat(G)≥3.

引理2 如果G(V，E)含C5，则χgat(G)≥3.

证明不然，根据引理1 1),χgat(G)≥2. 假设χgat(G)=2, 不是一般性，对于G(V，E)首先染其C5.事实上，令C5=v1v2v3v4v5v1且C(v1)={1}，则f(v2)=1,f(v2v3)=2，或f(v2)=2,f(v2v3)=1,或f(v2)=2,f(v2v3)=2，而f(v3)=2,f(v3v4)=2，或f(v3)=1,f(v3v4)=1根据如此染色，有

则有C(v5)={1}，{2}或C(v5)={1,2}，但v5与v1，v4是相邻的顶点，所以与一般邻点可区别全染色定义矛盾，故χgat(G)≥3.

定理1设Pn为n(n≥2)阶路，则

χgat(M(Pn))=3.

证明设Pn=v1v2…vn，分2种情况进行证明.

情形1 当n=2,注意到M(Pn)=C5，由引理2，χgat(M(Pn))=3[12-13].

则有

定理2设Cn是n(n≥3)阶圈，则

χgat(M(Cn))=3.

证明设Cn=v1v2…vnv1，分3种情况进行讨论.

情形1 当n=3时，M(C3)包含有K3, 按照引理1 2), 有χgat(M(C3))≥3.为证结论成立, 只需给出M(C3)的一个3-GAVDTC. 令f

易于验证f是M(C3)的一个3-GAVDTC. 所以χgat(M(Pn))=3.

情形2 当n≥4时, 根据引理2, 有χgat(M(Pn))≥3. 现在只需构造M(C3)的一个3-GAVDTC法f. 为此，从2个方面考虑.

情形(1) 当n≡0(mod 2)时, 令f

f(vivi+1)=1 i=1,2,…,n-1，f(vnv1)=1，

则

易见，f为M(Cn)的一个3-GAVDTC(n≡0(mod 2)). 所以结论成立.

情形(2) 当n≡1(mod 2)时,令f

f(vi)=1 i≡1(mod 2),f(vi)=3,i≡0(mod 2) i=1, 2,…,n-1,f(vn)=3，

f(vivi+1)=1 i=1,2,…,n-1，f(vnv1)=1，

则

显然,f是M(Cn)的一个3-GAVDTC(n≡1(mod 2)).所以结论成立.

定理3设Fn是有n+1(n≥2) 个顶点的扇, 则

χgat(M(Fn))=3.

f(vi)=1 i=0, 1, 2,…,n,f(vivi+1)=1 i=1, 2,…,n-1，

则

显然, f为M(Fn)的3-GAVDTC. 从而结论成立.

定理4设Wn是有n+1(n≥3)个顶点的轮,则

情形1 当n≡0(mod 2)时, 根据引理1 2),χgat(M(Wn))≥3. 为证结论成立, 只需构造M(Wn)的一个3-GAVDTC. 令f

f(vivi+1)=1 i=1,2,…,n-1，f(vnv1)=1，

则

显然，f是M(Wn)的3-GAVDTC. 从而结论成立.

情形 2 当n≡1(mod 2)时, χgat(M(Wn))≥4. 否则, 根据引理1 2),χgat(M(Wn))≥3. 令χgat(M(Wn))=3, 则所有顶点的色集必是{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}其中之一. 对于M(Wn)的轮Wn，不失一般性，首先固定顶点v0的色集为C(v0)={1}，由于每个vi都与v0相邻，所以顶点vi(i=1, 2,…,n)的色集必是{1, 2}, {1, 3}和{1, 2, 3}其中之一. 由所有的顶点组成圈Cn，且n是奇数，所以所有的顶点vi(i=1, 2,…,n)的色集含有{1, 2}, {1, 3}和{1, 2, 3},且这些色集是不能有重复色集相邻的按序排列下来.不妨令C(v1)={1,3},C(v2)={1, 2},C(vn)={1, 2, 3},则顶点vn-1的色集必然是C(vn-1)={1,2}或C(vn-1)={1,3}.

则

显然,f是M(Wn)的4-GAVDTC(n≡1(mod 2)).从而结论成立.

定理5设完全二部图为Km,n, 则

χgat(M(Km,n))=3.

证明令(X,Y)为Km,n的二部顶点集对. 根据引理2, χgat(M(Km,n))≥3.

首先, 用色1, 2和3染M(Km,n)的顶点集X和X′的所有顶点，用色1染所有的边，然后用色2染顶点集Y和Y′的所有顶点，最后用色3染顶点ω. 显然该f是M(Km,n)的3-GAVDTC. 结论成立.

推论1 设Sn=K1,n是有n+1(n≥2)个顶点的星, 则

χgat(M(Sn))=3.

证明根据定理5，结论显然.

由上述结论，关于Mycielski图的一般邻点可区别全色数，可得定理6.

定理6设G(V,E)为任意简单图, 则

χgat(G)≤χgat(M(G))≤χgat(G)+1.

[1] Bazgan C, Harkat-Benhamdine H, Li H, et al. On the Vertex-distinguishing proper edge-colorings of Graphs[J].J. Combin Theory: Ser B, 1999, 75(2): 288-301.

[2] Burris A C, Schelp R H. Vertex-distinguishing proper edge-colorings[J]. J. Graph Theory, 1997, 26(2):73-82.

[3] Balister P N, Piordan O M, Schelp R H.Vertex-distinguishing edge colorings of graphs[J].J. Graph Theory, 2003,42:95-105.

[4] Balister P N, Györi E, Lebel J, et al. Adjacent vertex distinguishing edge-colorings[J]. SIAM Journal on Discrete Mathematics, 2006, 21(1):237-250.

[5] Zhang Z F,Liu L Z, Wang J F. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15: 623-626.

[6] Zhang Z F, Chen X G, Li J W, et al. On adjacent-vertex-distinguishing total coloring of graphs[J].Sci. China Ser. A, 2005, 48(3):289-299.

[7] Chen X E, Zhang Z F, Yan J Z， et al. Adjacent-vertex-distinguishing total chromatic numbers on Mycielski graphs of several kinds of particular graphs[J]. Journal of Lanzhou University (Natural Sciences), 2005,41(2):117-122.

[8] 王继顺，邱泽阳，张忠辅，等．联图Fn∨Pm的邻点可区别全染色[J]. 应用数学学报，2006, 29(5): 879-884．

[9] Wang H Y. On the adjacent-vertex-distinguishing total chromatic number of the graph with Δ=3[J].Journalof Combinatorial Optimization, 2007, 14(1):87-109.

[10] Chen X E. On the adjacent vertex distinguishing total coloring numbers of graphs with Δ=3[J].DiscreteMathematics, 2008(308):4 003-4 007.

[11] Györi E, Hornak M, Palmer C. General neignbour-distinguishing number of a graph[J].Discrete Mathematics, 2008, 308(5):827-831.

[12] Zhang Z F, Yao B, Li J W, et al. General adjacent-vertex-distinguishing total coloring of graphs[EB/OL]. (2014-06-26).[2016-06-10].http://202.201.18.40:8080/mas5/.

[13] 严谦泰.关于图的一般邻点可区别全染色[J].系统科学与数学, 2010, 30(1):101-106.

[14] 田京京，贾伟，陈祥恩.若干图类的一般邻点可区别全染色算法及其MATLAB实现[J].数学的实践与认识, 2013, 43(15):227-233.

[15] Liu H M. Circular Chromatic Number and Myceilski Graphs[J]. Acta Mathematica Scientia,2006,26B(2):314-320.

[16] 王继顺. 图M(Pm)和M(Cm)的点可区别边色数[J].数学杂志，2012，32(2): 363-368.

[17] 马刚. 若干Mycielski图的点可区别均匀全色数[J].数学的实践与认识，2012, 42(9): 207-213.

[18] Bondy J A,Murty U S R. Graph Theory[M]. New York: Springer, 2008.

General Adjacent Vertex-distinguishing Total Coloring Chromatic Number of Mycielski Graphs

Wang Jishun

(School of Mathematics and Information Engineering, Lianyungang Teacher’s College, Lianyungang 222006, China)

Mycielski Graph; General adjacent vertex distinguishing total coloring; General adjacent vertex distinguishing total chromatic number

2016-06-22

国家自然科学基金(61170302)；连云港市第五期“521”人才培养工程资助项目