幾種特殊圖的均勻邊染色

萬慧敏，史小藝，王艷麗

（中國(guó)礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221008）

幾種特殊圖的均勻邊染色

萬慧敏，史小藝，王艷麗

（中國(guó)礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221008）

研究立方Halin圖以及一些倍圖的均勻邊染色，利用換色法、構(gòu)造法和歸納法得出：立方Halin圖和路的倍圖都是均勻的，星的倍圖都有均勻4-邊染色.

立方Halin圖；倍圖；均勻邊染色

1 引言及定義

本文僅討論有限無向簡(jiǎn)單圖，除聲明的特殊記號(hào)和術(shù)語外，均使用標(biāo)準(zhǔn)的圖論術(shù)語[1].圖的染色問題是圖論研究中的重要問題之一，有重大的理論價(jià)值和應(yīng)用背景.圖的均勻染色理論是圖的染色理論的一種推廣.本文給出了星nS、路nP的倍圖以及立方Halin圖均勻邊染色的情況.

關(guān)于Halin圖的概念有很多版本，其實(shí)質(zhì)是相同的，本文采用如下定義.

定義2 在平面內(nèi)嵌入一棵樹T，設(shè)樹T的每個(gè)內(nèi)部項(xiàng)點(diǎn)的度數(shù)至少是3，并且T至少有一個(gè)內(nèi)部頂點(diǎn).作一個(gè)圈C順次連接T的所有葉頂點(diǎn)，T的所有葉頂點(diǎn)組成C上的所有頂點(diǎn)，由此得到的平面圖G稱為Halin圖.

樹T稱為Halin圖G的特征樹，圈C稱為Halin圖G的伴隨圈，T的葉子頂點(diǎn)稱為G的外頂點(diǎn)，G的其他頂點(diǎn)稱為內(nèi)點(diǎn).去掉T的懸掛點(diǎn)及其關(guān)聯(lián)的邊后得到的圖仍是一棵樹，記為T′，令V′表示T′的懸掛點(diǎn)集合.若對(duì)任意的頂點(diǎn) v ∈ V（ G）都有 d（ v）= 3，則稱Halin圖G為立方Halin圖.

定義3[3]設(shè)G′為簡(jiǎn)單圖G的拷貝，設(shè)G的頂點(diǎn)為 ui，G′相應(yīng)的頂點(diǎn)為 vi，若滿足：

則稱 D（ G）為G′的倍圖.

引理1[4]設(shè)圖G為簡(jiǎn)單圖， k≥ 2.如果對(duì)任意 v∈ V（ G），有 d（ v） ≠ 0（ m odk ），則圖G存在k種顏色的均勻邊染色.

2 主要結(jié)果

定理1 對(duì)任意整數(shù) 3k≥ ，立方Halin圖G都有均勻k-邊染色.

定理2 設(shè)Pn為n階路（n ≥ 2），對(duì)任意整數(shù) k≥ 1， D（ Pn）都有均勻k-邊染色，即 D（ Pn）是均勻的.

由倍圖的定義易知：

由引理1易得 D（ Pn）存在均勻3-邊染色，下面只要給出 D（ Pn）的一個(gè)均勻2-邊染色和4-邊染色即可.

u1v2, u2v3,… ,un-1vn和v1u2, v2u3,… ,vn-1un分別交替染2和1.

u1u2, u2u3,… ,un-1un分別交替地染色1和4；v1v2, v2v3,…, vn-1vn分別交替地染色4和1；u1v2, u2v3,…,un-1vn和v1u2, v2u3,… ,vn-1un分別交替的染色3和2.

可以看出：當(dāng) n=2時(shí)， c（ u1）= c（ u2）= ｛1,3｝，c（ v1）= c（ v2）= ｛3,4｝；

定理3 對(duì) n+1階的星 Sn， D（ Sn）存在均勻4-邊染色.

證明 當(dāng) n=1時(shí) D（ S1）= C4，顯然由定理2可知存在均勻4-邊染色.

當(dāng) 2n≥ 時(shí)，由倍圖的定義易知：

顯然 D（ Sn）可以看成由n個(gè)4圈 u0ui, uiv0, v0vi, viu0（ i= 1,2,… ,n）組成的.要證明定理成立，只要給出 D（ Sn）的一個(gè)均勻4-邊染色即可.

設(shè)c= ｛0,1,2,3｝，構(gòu)造φ如下：

當(dāng)i≡ 0（ mod4）則4圈的4邊 u0ui、 uiv0、 v0vi、 viu0分別染色0、1、2、3，

當(dāng)i≡ 1（ mod4）則4圈的4邊 u0ui、 uiv0、 v0vi、 viu0分別染色1、2、3、0，

當(dāng)i≡ 2（ mod4）則4圈的4邊 u0ui、 uiv0、 v0vi、 viu0分別染色3、0、1、2，

綜上所述， D（ Sn）存在均勻4-邊染色，定理得證.

[1]BONDY J A,MURTY U S R.Graph theory with application[M].London:Macmillan Press,1976:1-200.

[2]宋慧敏，吳建良.Halin圖的均勻邊染色[J].山東大學(xué)學(xué)報(bào)，2003,38:31-34.

[3]ZHANG Zhongfu,QIU Pengxiang,ZHANG Donghan,et al.The double graph and the complement double graph of a graph[J].Advances in Mathematics,2008,37(3):303-310.

[4]HILTON A J W,WERRA de D.A sufficient condition for equitable edge-colourings of simple graphs[J].Discrete Mathematics,1994,128:179-201.

Equitable Edge-Coloring of Some Special Graphs

WAN Hui-min,SHI Xiao-yi,WANG Yan-li

(College of Science,China University of Mining and Technology,Xuzhou 221008,China)

The equitable edge-coloring of cubic Halin graphs and some double graphs are studied by using induction,interchange colors method and construction.The results indicate that cubic Halin graphs and the double graphs of path are equitable, and the double graphs of star have an equitable edge-coloring with 4 colors.

cubic Halin graph;double graph;equitable edge-coloring

1006-7302（2012）04-0006-03

O157.5

A

2012-07-02

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.11001265）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目（2010LKSX06）

萬慧敏（1988—），女，山東濟(jì)寧人，在讀碩士生，主要從事圖論方面的研究.

熊玉濤]