杨晓亚

(天水师范学院数学与统计学院,甘肃 天水 741001)

图Pn□Cm的邻点可区别I-全染色

杨晓亚

(天水师范学院数学与统计学院,甘肃 天水 741001)

通过对图Pn□Cm的积图的邻点可区别全染色研究,来进一步验证邻点可区别全染色的猜想.应用构造具体染色的方法给出了图Pn□Cm的积图的邻点可区别全染色.得到了图Pn□Cm的积图的邻点可区别全染色的色数.

I-全染色;邻点可区别I-全染色;邻点可区别I-全色数

1 引言

图的染色是图论的重要研究内容之一,由计算机科学和信息科学等所产生的点可区别边染色[1-9],邻点可区别边染色(或邻强边染色)[24]及邻点可区别全染色[5-6]等都是十分困难的问题,至今文献甚少.在此基础之上,张忠辅等人进一步提出了图的新染色概念,图的邻点可区别I-全染色是其中之一[7].本文给出了路Pm和圈Cn的Cartesian积图的邻点可区别I-全色数.

定义1.1[6]设G是阶至少为2的连通图,k为正整数,f是图G的使用颜色为1,2,···,k的正常全染色.∀x∈V(G),令C(x)表示在f下点x的颜色及与x关联的全体边的颜色构成的集合,称之为在全染色f下点x的色集合.如果∀uv∈E(G),有C(u)̸=C(v),则f称为G的k-邻点可区别全染色.称

为G的邻点可区别全色数.

定义1.2[7]设G是阶至少为2的连通图,k为正整数,f是图G的使用颜色为1,2,···,k的全染色.如果G的任意相邻的点染不同的颜色,并且G的任意相邻的边染不同的颜色,那么称f为G的I-全染色.设f是G的I-全染色,∀x∈V(G),令C(x)表示在f下点x的颜色及与x关联的全体边的颜色构成的集合,称之为在f下点x的色集合.如果∀uv∈E(G),有C(u)̸=C(v),则f称为G的k-邻点可区别I-全染色(简记为k-AVDIT染色).称

2 主要结果

[1]Favaron O,Li H,Schelp R H.Strong edge colorings of graphs[J].Discrete Mathematica,1996,159:103-109.

[2]Zhang Zhongfu,Liu Linzhong,Wang Jianfang.Ad jacent strong edge coloring of graphs[J].App lied M athematica Letters,2002,15:623-626.

[3]Li Jingwen,Zhang Zhongfu,Chen X iang′en,et al.A note on ad jacent strong edge coloring of K(n,m)[J]. Acta M athem aticae App licatae Sinica(English Series),2006,22(2):273-276.

[4]Zhang Zhongfu,Li M uchun,Yao Bing,et al.On the vertex distinguishing equitable edge-colouring of graphs[J].A rs Combinatoria,2008,86:193-200.

[5]陈祥恩.关于图rK2∨Ks的邻点可区别全色数[J].兰州大学学报,2007,43(5):91-93.

[6]陈祥恩,张忠辅.关于图K2n+1−E(2K2)的邻点可区别全色数[J].兰州大学学报,2005,41(6):102-105.

[7]Zhang Zhongfu,WoodallD R,Yao Bing,et al.Ad jacent vertex-distinguishing I-totalcoloring ofgraphs[EB/OL]. (2008-06-12)[2008-07-24]http://202.201.18.40:8080/m as5/.

[8]Bondy J A,Murty U SR.Graph Theory[M].London:Springer,2008.

[9]王治文,文飞,杨随义,等.图K2nE(F5)(n≥13)的点可区别边染色[J].河南师范大学学报,2010,38(6):1-3.

Adjacent vertex-d istinguish ing I-total colorings of Pn□Cm

Yang Xiaoya

(Departm ent of M athem atics,T ianshui Norm al University,T ianshui 741001,China)

The con jecture on ad jacent vertex-distinguishing I-total colorings of graphs is proved through adjacent vertex-distinguishing I-total colorings of Pn□Cm.The ad jacent vertex-distinguishing I-total colorings of Pn□ Cmis given by m ethod of constructing concrete coloring.The ad jacent vertex-distinguishing I-total chrom atic numbers of Pn□Cmis obtained.

I-total coloring,ad jacent vertex-distinguishing I-total coloring, ad jacent vertex-distinguishing I-total chromatic number

O157.5

A

1008-5513(2012)06-0757-08

2012-06-15.

甘肃省自然科学基金(096RJZE106);天水师范学院中青年教师科研资助项目(TSA 1102).

杨晓亚(1977-),硕士,讲师,研究方向:计算机网络控制与图的染色.

2010 M SC:05C15