直积图Pm∧Sn、Pm∧Fn与Pm∧Wn的第一类弱全染色

王大胄, 张生智

(甘肃民族师范学院 数学系, 甘肃 合作 747000)

直积图Pm∧Sn、Pm∧Fn与Pm∧Wn的第一类弱全染色

王大胄, 张生智

(甘肃民族师范学院 数学系, 甘肃 合作 747000)

图染色是图论的重要组成部分,它有着一定的理论意义和实际应用背景.给出了直积图Pm∧Sn、Pm∧Fn与Pm∧Wn的第一类弱全染色数,并分别给出了构造性的证明,进而验证了这些图对第一类弱全染色猜想成立.

直积图; 第一类弱全染色; 第一类弱全染色数; 构造函数法; 路与星; 路与扇; 路与轮

图的染色是图论的重要研究内容之一,由计算机科学和信息科学等所产生的一般点可区别染色[1]、邻点可区别边染色[2-3]、及D(β)点可区别边染色[4]、点可区别边染色[5-6]、邻点可区别全染色[7]等都是十分困难的问题,至今文献甚少.在此基础上,Zhang Z. F.等[8]进一步提出了第一类全染色概念,并得出了重要结论.本文给出了顶点数均为m(n-1)的Pm∧Sn、Pm∧Fn与Pm∧Wn的直积图的第一类弱全染色数.

1 预备知识

定义 1[8]对于阶数不小于2的连通图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,如果f满足：

1) ∀uv∈E(G),u≠v,有f(u)≠f(v);

2) ∀uw,vw∈E(G),u≠v,有f(uw)≠f(vw),

则称f是图G的第一类弱全染色,(简记作k-FWTC).记χfwt(G)=min{k|G有k-第一类弱全染色}为G的第一类弱全染色数.

定义 2[9]直积G∧H满足：

V(G∧H)=V(G)×V(H);

E(G∧H)={(u1,v1)(u2,v2)|u1u2∈E(G)且v1v2∈E(H)}.

定义 3[10]图G是一棵树,且它有一个顶点邻接于其他所有顶点,则图G称为星型图,记n阶星为Sn(n≥2).

定义 4[10]设Pn-1是有n-1个顶点的路,P1与Pn-1的联图P1∨Pn-1称为扇图,记n阶扇为Fn(n≥3).

定义 5[10]Wn=Cn-1·V0表示具有n个顶点的轮图,其中Cn-1表示有n-1个顶点的圈,记Cn-1=v1v2…vn-1v1,Cn-1的每一个顶点都与中心顶点V0连接.

猜想 1[11](全染色猜想) 对任意的简单图G,有χT(G)≤Δ(G)+2.

猜想 4[7]对于阶数不小于2的简单连通图G,则有χat(G)≤Δ(G)+3.

引理 1[8]对简单图G有

χfwt(G)≥max{χ′(G),χ(G)}.

2 主要结论

为了书写方便,记顶点(ui,vj)=wij,边((ui,vj),(uk,vl))=wijwkl.

定理 1 对于m阶路Pm(m≥2),n+1阶星Sn(n≥2),则有

证明 情况1 当m=2时,由引理1知,χfwt(Pm∧Sn)≥n,为证明χfwt(Pm∧Sn)=n,仅需给出Pm∧Sn的一个n-FWTC法,如下设f为:

f(wi,0)=1,i=1,2;

f(wi,j)=2,i=1,2,j=1,2,…,n;

f(w1,0w2,j)=f(w2,0w1,j)=j,j=1,2,…,n.

显然f是Pm∧Sn的一个n-FWTC法.

情况2 当m≥3时,由引理1知,χfwt(Pm∧Sn)≥2n,为证明χfwt(Pm∧Sn)=2n,仅需给出Pm∧Sn的一个2n-FWTC法,如下设f为:

f(wi,0)=1,i=1,2,…,m;

f(wi,j)=2,i=1,2,…,m,j=1,2,…,n;

f(wi,0wi+1,j)=f(wi+1,0wi,j)=

显然f是Pm∧Sn的一个2n-FWTC法.

定理 2 对于m阶路Pm(m≥2),n+1阶扇Fn(n≥3),则有

证明 情况1 当m=2时,由引理1知,χfwt(Pm∧Fn)≥n,为证明χfwt(Pm∧Fn)=n,仅需给出Pm∧Fn的一个n-FWTC法,如下设f为:

f(wi,0)=1,i=1,2;

f(wi,j)=2,i=1,2,j=1,3,5,…,n;

f(wi,j)=3,i=1,2,j=2,4,6,…,n;

f(w1,jw2,j+1)=1,j=0,1,2,…,n-1;

f(w2,0w1,n)=1;

f(w2,jw1,j+1)=2,j=0,1,2,…,n-1;

f(w1,0w2,n)=2;

f(w2,0w1,j)=f(w1,0w2,j)=j+1,

j=2,3,4,…,n-1.

显然f是Pm∧Fn的一个n-FWTC法.

情况2 当m≥3时,由引理1知,χfwt(Pm∧Fn)≥2n,为证明χfwt(Pm∧Fn)=2n,仅需给出Pm∧Fn的一个2n-FWTC法,如下设f为:

f(wi,0)=1,i=1,2,…,m;

f(wi,jwi+1,j+1)=1;f(wi+1,0wi,n)=1,

i=1,3,5,…,m,j=0,1,2,…,n-1;

f(wi+1,jwi,j+1)=2;f(wi,0wi+1,n)=2,

i=1,3,5,…,m,j=0,1,2,…,n-1;

f(wi+1,0wi,j)=f(wi,0wi+1,j)=j+1,

i=1,3,5,…,m,j=2,3,4,…,n-1;

f(wi+1,0wi,n)=n+1,i=2,4,6,…,m;

f(wi,jwi+1,j+1)=n+1,

i=2,4,6,…,m,j=0,1,2,…,n-1;

f(wi,0wi+1,n)=n+2,i=2,4,6,…,m;

f(wi+1,jwi,j+1)=n+2,

i=2,4,6,…,m,j=0,1,2,…,n-1;

f(wi,0wi+1,j)=f(wi+1,0wi,j)=n+j+1,

i=2,4,6,…,m,j=2,3,4,…,n-1.

显然f是Pm∧Sn的一个2n-FWTC法.定理得证.

定理 3 对于m阶路Pm(m≥2),n+1阶轮Wn(n≥3),则有

证明 情况1 当m=2,n=3时,由引理知,χfwt(Pm∧Wn)≥4,为证明χfwt(Pm∧Wn)=4,仅需给出Pm∧Wn的一个4-FWTC法,如下设f为:

f(wi,0)=1;f(wi,1)=2;

f(wi,2)=3;f(wi,3)=4,i=1,2;

f(w1,jw2,j+1)=1,j=0,1,2;

f(w2,0w1,3)=1;

f(w2,jw1,j+1)=2,j=0,1,2;

f(w1,0w2,3)=2;

f(w1,0w2,2)=f(w2,0w1,2)=

f(w1,1w2,3)=f(w2,1w1,3)=3.

显然f是Pm∧Wn的一个4-FWTC法.

情况2 在P2∧Fn(n≥4)的基础上,添加2条边f(w1,1w2,n)=f(w2,1w1,n)=3.定理可得证.

情况3 在Pm∧Fn(m≥3)的基础上,添加2(n-1)条边,即

f(wi,1wi+1,n)=f(wi+1,1wi,n)=

显然f是Pm∧Wn的一个2n-FWTC法.定理便可得证.

图与图之间的运算还有很多,如并、粘合、合成积、笛卡尔积等,由于篇幅有限,本文只讨论了上述直积图的染色问题.

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

[2] BALISTER P N, GYORI E, LEHEL J, et al. Adjacent vertex distinguishing edge-colorings[J]. Siam J Discrete Math,2007,21(1):237-250.

[3] 张婷,李沐春,徐宝根,等. 关于Cm×C5n的全染色数和邻强边色数[J]. 兰州交通大学学报(自然科学版),2007,26(6):124-126.

[4] LI J W, ZHANG Z F, CHEN X E, et al.D(β)-vertex-distinguishing proper edge-coloring of graphs[J]. Acta Math Sinca,2006,49(3):703-708.

[5] ZHANG Z F, QIU P X, XU B G, et al. Vertex-distinguishing total coloring of graphs[J]. Arscomb,2008,87:33-45.

[6] 张忠辅,李敬文,陈祥恩. 图的距离不大于的任意两点可区别的全染色[J]. 中国科学,2006,A49(10):1430-1440.

[7] ZHANG Z F, LIU L Z, WANG J F. Adjacent strong edge coloring of graphs[J]. Appl Math Lett,2002,15(5):623-626.

[8] ZHANG Z F. On the first kind weak total coloring of graphs[EB/OL]. [2008-10-12].http://202.201.18.40:8080/mas5/.

[9] CHEN X E, ZHANG Z F. Adjacent Vertex-distinguishing total chromatic number ofK2n+1-E(2K2)[J]. 兰州大学学报(自然科学版),2005,41(6):102-105.

[10] 于玲,叶永升. 路和圈的联的Wiener指数[J]. 淮北师范大学学报(自然科学版),2011,32(1):1-3.

[11] BONDY J A, MURTY U S R. Graph theory with applications[J]. Macmillan,1976,28(1):237-238.

[12] 张忠辅,王建芳. 关于图的全着色的一个综述[J]. 数学进展,1992,21(4):390-397.

[13] BALISTER N, PIORDAN O M, SCHELP R H. Vertex- distinguishing proper edge colorings of graphs[J]. Graph Theory,2003,42(2):95-105.

[14] ZHANG Z F, CHEN X E, LI J W, et al. On adjacent-vertex-distinguishing total coloring of graphs[J]. Sci China,2005,A48(3):289-299.

[15] HATAMI H.Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]. J Combinatorial Theory,2005,B95(2):246-256.

[16] WANG H Y. On the adjacent vertex-distinguishing total chromatic numbers of the graphs withΔ(G)=3[J]. J Combinatorial Optimization,2007,14(1):87-109.

2010 MSC：05C10

(编辑 李德华)

On a Number of the First Weak Total Coloring of Direct Product GraphPm∧Sn,Pm∧FnandPm∧Wn

WANG Dazhou, ZHANG Shengzhi

(DepartmentofMathematics,GansuNormalUniversityforNationalities,Hezuo747000,Gansu)

Graph coloring is an important part of the graph theory, which has a certain theoretical and practical application background. In this paper, we give the first kind weakly total coloring number of direct product graphPm∧Sn,Pm∧FnandPm∧Wnby using a constructive method, and then verify these graphs to set up the first weak total coloring conjecture.

direct product graph; first weak total coloring; first weak total chromatic number; the constructor method; road and stars; road and fan; roads and wheels

2016-04-23

甘肃省教育科学“十二五”规划课题(GS[2013]GHB11096)

王大胄(1973—),男,教授,主要从事数学教学与研究,E-mail:wangdazhou_mgx@163.com

O157.5

A

1001-8395(2017)03-0313-03

10.3969/j.issn.1001-8395.2017.03.006