楊曉亞

(天水師范學院數學與統(tǒng)計學院,甘肅 天水 741001)

圖Pn□Cm的鄰點可區(qū)別I-全染色

楊曉亞

(天水師范學院數學與統(tǒng)計學院,甘肅 天水 741001)

通過對圖Pn□Cm的積圖的鄰點可區(qū)別全染色研究,來進一步驗證鄰點可區(qū)別全染色的猜想.應用構造具體染色的方法給出了圖Pn□Cm的積圖的鄰點可區(qū)別全染色.得到了圖Pn□Cm的積圖的鄰點可區(qū)別全染色的色數.

I-全染色;鄰點可區(qū)別I-全染色;鄰點可區(qū)別I-全色數

1 引言

圖的染色是圖論的重要研究內容之一,由計算機科學和信息科學等所產生的點可區(qū)別邊染色[1-9],鄰點可區(qū)別邊染色(或鄰強邊染色)[24]及鄰點可區(qū)別全染色[5-6]等都是十分困難的問題,至今文獻甚少.在此基礎之上,張忠輔等人進一步提出了圖的新染色概念,圖的鄰點可區(qū)別I-全染色是其中之一[7].本文給出了路Pm和圈Cn的Cartesian積圖的鄰點可區(qū)別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-鄰點可區(qū)別全染色.稱

為G的鄰點可區(qū)別全色數.

定義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-鄰點可區(qū)別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的鄰點可區(qū)別全色數[J].蘭州大學學報,2007,43(5):91-93.

[6]陳祥恩,張忠輔.關于圖K2n+1?E(2K2)的鄰點可區(qū)別全色數[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)的點可區(qū)別邊染色[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