几种特殊图的均匀边染色

万慧敏，史小艺，王艳丽

（中国矿业大学 理学院，江苏 徐州 221008）

几种特殊图的均匀边染色

万慧敏，史小艺，王艳丽

（中国矿业大学 理学院，江苏 徐州 221008）

研究立方Halin图以及一些倍图的均匀边染色，利用换色法、构造法和归纳法得出：立方Halin图和路的倍图都是均匀的，星的倍图都有均匀4-边染色.

立方Halin图；倍图；均匀边染色

1 引言及定义

本文仅讨论有限无向简单图，除声明的特殊记号和术语外，均使用标准的图论术语[1].图的染色问题是图论研究中的重要问题之一，有重大的理论价值和应用背景.图的均匀染色理论是图的染色理论的一种推广.本文给出了星nS、路nP的倍图以及立方Halin图均匀边染色的情况.

关于Halin图的概念有很多版本，其实质是相同的，本文采用如下定义.

定义2 在平面内嵌入一棵树T，设树T的每个内部项点的度数至少是3，并且T至少有一个内部顶点.作一个圈C顺次连接T的所有叶顶点，T的所有叶顶点组成C上的所有顶点，由此得到的平面图G称为Halin图.

树T称为Halin图G的特征树，圈C称为Halin图G的伴随圈，T的叶子顶点称为G的外顶点，G的其他顶点称为内点.去掉T的悬挂点及其关联的边后得到的图仍是一棵树，记为T′，令V′表示T′的悬挂点集合.若对任意的顶点 v ∈ V（ G）都有 d（ v）= 3，则称Halin图G为立方Halin图.

定义3[3]设G′为简单图G的拷贝，设G的顶点为 ui，G′相应的顶点为 vi，若满足：

则称 D（ G）为G′的倍图.

引理1[4]设图G为简单图， k≥ 2.如果对任意 v∈ V（ G），有 d（ v） ≠ 0（ m odk ），则图G存在k种颜色的均匀边染色.

2 主要结果

定理1 对任意整数 3k≥ ，立方Halin图G都有均匀k-边染色.

定理2 设Pn为n阶路（n ≥ 2），对任意整数 k≥ 1， D（ Pn）都有均匀k-边染色，即 D（ Pn）是均匀的.

由倍图的定义易知：

由引理1易得 D（ Pn）存在均匀3-边染色，下面只要给出 D（ Pn）的一个均匀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.

可以看出：当 n=2时， c（ u1）= c（ u2）= ｛1,3｝，c（ v1）= c（ v2）= ｛3,4｝；

定理3 对 n+1阶的星 Sn， D（ Sn）存在均匀4-边染色.

证明 当 n=1时 D（ S1）= C4，显然由定理2可知存在均匀4-边染色.

当 2n≥ 时，由倍图的定义易知：

显然 D（ Sn）可以看成由n个4圈 u0ui, uiv0, v0vi, viu0（ i= 1,2,… ,n）组成的.要证明定理成立，只要给出 D（ Sn）的一个均匀4-边染色即可.

设c= ｛0,1,2,3｝，构造φ如下：

当i≡ 0（ mod4）则4圈的4边 u0ui、 uiv0、 v0vi、 viu0分别染色0、1、2、3，

当i≡ 1（ mod4）则4圈的4边 u0ui、 uiv0、 v0vi、 viu0分别染色1、2、3、0，

当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].山东大学学报，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

国家自然科学基金资助项目（No.11001265）；中央高校基本科研业务费专项基金资助项目（2010LKSX06）

万慧敏（1988—），女，山东济宁人，在读硕士生，主要从事图论方面的研究.

熊玉涛]