直積圖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