两类树图的Hamiltonian色数

申玉发，高 烨，王 莹，武利猛

(河北科技师范学院数学与信息科技学院，河北 秦皇岛，066004)



两类树图的Hamiltonian色数

申玉发，高 烨，王 莹，武利猛

(河北科技师范学院数学与信息科技学院，河北 秦皇岛，066004)

一个n阶连通图G的Hamiltonian染色是从G的顶点集V(G)到正整数集(称为颜色集)的一个映射c，使得对于G的任意2个不同的顶点u和v满足|c(u)-c(v)|+D(u,v)≥n-1，其中D(u,v)表示G中u到v的最长路径的长度。对一个Hamiltonian染色c，将max{c(u):u∈V(G)}称为c的值，记作hc(c)。将min{hc(c):c是G的任意Hamiltonian染色}称为G的Hamiltonian色数，记作hc(G)。本次研究得到了满足max{D(u,v)|u,v∈V(G)的d-重似星树和广义双星这两类树图的Hamiltonian色数的确切值。

Hamiltonian染色；Hamiltonian色数；d-重似星树；广义双星

2001年，Chartrand等[1,2]基于无线电台的频道分配问题提出了Radio-k-染色的概念。进一步，2005年，Chartrand等[3,4]又在Radio-k-染色概念的基础上提出了Hamiltonian染色的概念。一个n阶连通图G的Hamiltonian染色是从G的顶点集V(G)到正整数集(称为颜色集)的一个映射c，使得对于G的任意2个不同的顶点u和v满足|c(u)-c(v)|+D(u,v)≥n-1，其中D(u,v)表示G中u到v的最长路径的长度。对一个Hamiltonian染色c，将max{c(u):u∈V(G)}称为c的值，记作hc(c)。将min{hc(c):c是G的任意Hamiltonian染色}称为G的Hamiltonian色数，记作hc(G)。如果G的一个Hamiltonian染色c满足hc(c)=hc(G)，则称c为G的最小的Hamiltonian染色。

1 预备知识

1.1 两类特殊树图的概念

似星树以及d-重似星树的定义由文献[8]提出，文献[8]中限定了d≥3。笔者从另一角度(在似星树的定义中允许d=2)给出相应的概念，并引入标准似星树及标准d-重似星树的概念。

定义1 将一个顶点u0与d(d≥2)条长度分别为mi(mi≥1,i=1,2,…,d)的路Pi的一个端顶点连一条边，所得到的树图称为似星树(或称为广义星)，记作S(u0:m1,m2,…,md)，并称u0为该似星树的根(或称为星心)，称路Pi(i=1,2,…,d) ()为似星树的悬挂路。特别地，若对任意的i=1,2,…,d，均有mi=m，则称该似星树为标准似星树，记作S(u0:m(d))。

定义2 设似星树S0(u0:m1,m2,…,md)的根u0的度d≥3，在其第i(i=1,2,…,d)条悬挂路的1度顶点与一个似星树Si(ui:m1,…,mi-1,mi+1,…,md)的根ui粘连所得到的树图称为d-重似星树，记作S(S0(u0):m1,m2,…,md)。特别地，若对任意的i=1,2,…,d，均有mi=m，即S0(u0:m1,m2,…,md)是标准似星树S(u0:m(d))，则称相应的d-重似星树为标准d-重似星树，记作S(S0(u0):m(d))。

1.2 一些引理

对于图G的一个给定的顶点序列σ:v1,v2,…,vn，定义G的顶点集V(G)到正整数集的一个映射cσ：

cσ(v1)=1,cσ(vi+1)-cσ(vi)=(n-1)-D(vi,vi+1), 1≤i≤n-1

(1)

关于似星树，建立如下引理。

引理2 在一个似星树G=S(x;l1,l2,…,lp)中，如果

(2)

则在G-x中存在一个顶点序列σ0，使σ0中任意个相邻顶点不在G的同一悬挂路上。

证明 记G的第i(i=1,2,…,p)条悬挂路上的顶点为xi1,xi2,…,xili。下面对G中悬挂路个数p用数学归纳法来证明。

当l1=l2时，在G-x中存在一个顶点序列σ0:x1l1,x2l2;x1(l1-1),x2(l2-1); …;x11,x21，使得σ0中任意个相邻顶点不在G的同一悬挂路上。

当l1=l2+1时，在G-x中存在一个顶点序列σ0:x1l1,x2l2;x1(l1-1),x2(l2-1); …;x12,x21;x11，使得σ0中任意2个相邻顶点不在G的同一悬挂路上。

令p≥3，假设引理2的结论在似星树的悬挂路个数p=n-1时成立。当p=n时，不妨设l1≥ln≥…≥ln≥1。如果G是标准的似星树，即l1=l2=…,=ln，则显然在G-x中存在一个顶点序列σ0:x1l1,x2l2,…,xnln;x1(l1-1),x2(l2-1),…,xn(ln-1); …;x11,x21,…,xn1，使得σ0中任意2个相邻顶点不在G的同一悬挂路上。否则，一定有l1-ln≥1。此时，可以经ln步如下递归地构造均满足引理2条件(2)的ln个似星树G(i)，i=1,2,…,ln。

断言G(1)满足引理2与之相应的条件(2)式。

2 d-重似星树的Hamiltonian色数

断言1 对于G的任意顶点序列σ:v1,v2,…,vn，有

且上式等号成立当且仅当u0∈V(Pi,i+1)(i=1,2,…,n-1)，其中Pi,i+1表示从vi到vi+1的路。

事实上，由G的结构可知，对任意i(i=1,2,…,n-1) ，如果u0∈V(Pi,i+1)，则D(vi,vi+1)=D(vi,u0)+D(u0,vi+1)；否则D(vi,vi+1)

且上式等号成立当且仅当u0∈V(Pi,i+1)(i=1,2,…,n-1)。因此，断言1成立。

断言2 存在G的一个顶点序列σ*:v1,v2,…,vn，满足v1=u0，vn∈N(u0)且u0∈V(Pi,i+1)(i=1,2,…,n-1)，其中Pi,i+1表示从vi到vi+1的路，使

事实上，据断言1，如果G的一个顶点序列σ:v1,v2,…,vn满足u0∈V(Pi,i+1)(i=1,2,…,n-1)，并且D(v1,u0)+D(vn,u0)达到它的最小值，那么D(σ)=D(G)。显然，对G的任意一个顶点序列σ:v1,v2,…,vn，有D(v1,u0)+D(vn,u0)≥1，并且对于G的满足v1=u0，vn∈N(u0)且u0∈V(Pi,i+1)(i=1,2,…,n-1)的每一个顶点序列σ*:v1,v2,…,vn，有D(v1,u0)+D(vn,u0)=1。

v1=u0;

…………………………………………；

vn-d+1=u0,11,vn-d+2=u0,21,…,vn=u0,d1。

推论1 对标准d-重似星树G=S(S0(u0):m(d))，有

hc(G)=d(d3-3d+2)m2+d2(2d-3)m+d2-2d+2。

证明 根据标准d-重似星树的定义，在定理1中对任意的i=1,2,…,d，令mi=m，即得推论1的结论。

3 非齐次广义双星的Hamiltonian色数

图1 S(S0(u0):m1,m2,…,md) 图2 S2(x:l1,l2,…,lp; y:m1,m2,…,mq)

断言3 对于G的任意顶点序列σ:v1,v2,…,vn，有

上式等号成立当且仅当x∈V(Pi,i+1)(i=1,2,…,n-1)，其中Pi,i+1表示从vi到vi+1的路。

事实上，对任意i(i=1,2,…,n-1)，如果x∈V(Pi,i+1)，则D(vi,vi+1)=D(vi,x)+D(x,vi+1)，否则D(vi,vi+1)<(vi,x)+D(x,vi+1)，因此

且上式等号成立当且仅当x∈V(Pi,i+1)(i=1,2,…,n-1)。因此，断言3成立。

断言4 存在G的一个顶点序列σ*:v1,v2,…,vn，满足v1=x，vn∈N(x)且x∈V(Pi,i+1)(i=1,2,…,n-1)，其中Pi,i+1表示从vi到vi+1的路，使得

事实上，据断言3，如果G的一个顶点序列σ:v1,v2,…,vn满足x∈V(Pi,i+1)(i=1,2,…,n-1)，并且D(v1,x)+D(vn,x)达到它的最小值，那么D(σ)=D(G)。显然，对G的任意一个顶点序列σ:v1,v2,…,vn，有D(v1,x)+D(vn,x)≥1，并且对于G的满足v1=x,vn∈N(x)且x∈V(Pi,i+1)(i=1,2,…,n-1)的每一个顶点序列σ*:v1,v2,…,vn，有D(v1,x)+D(vn,x)=1。

当t=0时，有|Vx|=|Vy|。易于发现存在G的一个顶点序列σ*:v1,v2,…,vn，其中

v1=x;v2∈Vy,v3∈Vx;v4∈Vy,v5∈Vx; …,vn-2∈Vy,vn-1∈Vx;vn=y

σ*满足v1=x，vn∈N(x)且x∈V(Pi,i+1)(i=1,2,…,n-1)。

可见，在t≥0时，总存在G的一个顶点序列σ*:v1,v2,…,vn满足v1=x，vn∈N(x)且vn∈N(x)(i=1,2,…,n-1)，从而有D(v1,x)+D(vn,x)=1，且

因此，断言4成立。

注意到n=∑1≤i≤pli+∑1≤j≤qmj+2，由断言4及引理1，有

推论2 对齐次广义双星G=S2(x:l(p);y:l(q))，有

hc(G)=l2(p+q)(p+q-1)+l(p-q)+1。

证明 根据齐次广义双星的定义，在定理2中对任意的i=1,2,…,p，j=1,2,…,q，令li=mj=l，即得推论2的结论。

[1] Gary Chartrand,David Erwin,Ping Zhang.Radio Labelings of Graphs[J].Bulletin of the ICA,2001,33:77-85.

[2] Gary Chartrand,David Erwin,Ping Zhang.A Graph Labelings Problem Suggested by FM Channel Restrictions[J].Bulletin of the ICA,2005,43:43-57.

[3] Gary Chartrand,Ladislay Nebesky,Ping Zhang.Hamiltonian Colorings of Graphs[J].Discrete Applied Mathematics,2005,146:257-272.

[4] Gary Chartrand,Ladislay Nebesky,Ping Zhang.On Hamiltonian Colorings of Graphs[J].Discrete Mathematics,2005,290:133-143.

[5] Gary Chartrand,Ladislay Nebesky,Ping Zhang.A Survey of Hamiltonian Colorings of Graphs[J].Congressus Numerantium,2004,169:179-192.

[6] R Khennoufa,O Tongi.A Note on Radio Antipodal Colourings of Paths[J].Math Bohem,2005,130:277-282.

[7] Yufa Shen,Wenjie He,Xue Li,et al.On Hamiltonian Colorings for Some Graphs[J].Discrete Applied Mathematics,2008,156(15):3 028-3 034.

[8] Wu Tingzeng,Hu Shengbiao.On the Spectral Radii ofm-Starlike Tree[J].Operations Research Transactions,2011,15(3):45-50.

[9] Béla Bollobás.现代图论[M].北京：科学出版社,2001.

(责任编辑：朱宝昌)

Hamiltonian Chromatic Number for Two Classes of Tree Graphs

SHEN Yu-fa,GAO Ye,WANG Ying,WU Li-meng

(School of Mathematics and Information Science & Technology，Hebei Normal University of Science & Technology，Qinhuangdao Hebei，066004，China)

A Hamiltonian coloring of a connected graphGof ordernis an assignmentcof colors (positive integers) to the vertices ofGsuch thatc(u)-c(v)|+D(u,v)≥n-1 for every two distinct verticesuandvofG, whereD(u,v) is the length of a longestu-vpath inG. For an Hamiltonian coloringc, the value of isc, denoted byhc(c), while the Hamiltonian chromatic number ofGis min{hc(c):cis taken over all humiltonian colorings ofG}, denoted byhc(G). In this paper, we obtain the exact values of Hamiltonian chromatic number ford-starlike trees and generalized double stars, as two classes of tree graphs.

Hamiltonian coloring; Hamiltonian chromatic number;d-starlike trees; generalized double stars

10.3969/J.ISSN.1672-7983.2015.02.001

河北省自然科学基金项目(项目编号：A2015407063)；秦皇岛市科学技术研究与发展计划项目(项目编号：201401A038)，河北科技师范学资助计划项目(项目编号：CXTD2012-08；2013YB008)。

2015-04-12; 修改稿收到日期: 2015-05-12

O157.5

A

1672-7983(2015)02-0001-06

申玉发(1965-)，教授，博士。主要研究方向：图论与网络最优化。