兩類樹圖的Hamiltonian色數(shù)

申玉發(fā)，高 燁，王 瑩，武利猛

(河北科技師范學(xué)院數(shù)學(xué)與信息科技學(xué)院，河北 秦皇島，066004)

?

兩類樹圖的Hamiltonian色數(shù)

申玉發(fā)，高 燁，王 瑩，武利猛

(河北科技師范學(xué)院數(shù)學(xué)與信息科技學(xué)院，河北 秦皇島，066004)

一個(gè)n階連通圖G的Hamiltonian染色是從G的頂點(diǎn)集V(G)到正整數(shù)集(稱為顏色集)的一個(gè)映射c，使得對(duì)于G的任意2個(gè)不同的頂點(diǎn)u和v滿足|c(u)-c(v)|+D(u,v)≥n-1，其中D(u,v)表示G中u到v的最長(zhǎng)路徑的長(zhǎng)度。對(duì)一個(gè)Hamiltonian染色c，將max{c(u):u∈V(G)}稱為c的值，記作hc(c)。將min{hc(c):c是G的任意Hamiltonian染色}稱為G的Hamiltonian色數(shù)，記作hc(G)。本次研究得到了滿足max{D(u,v)|u,v∈V(G)的d-重似星樹和廣義雙星這兩類樹圖的Hamiltonian色數(shù)的確切值。

Hamiltonian染色；Hamiltonian色數(shù)；d-重似星樹；廣義雙星

2001年，Chartrand等[1,2]基于無線電臺(tái)的頻道分配問題提出了Radio-k-染色的概念。進(jìn)一步，2005年，Chartrand等[3,4]又在Radio-k-染色概念的基礎(chǔ)上提出了Hamiltonian染色的概念。一個(gè)n階連通圖G的Hamiltonian染色是從G的頂點(diǎn)集V(G)到正整數(shù)集(稱為顏色集)的一個(gè)映射c，使得對(duì)于G的任意2個(gè)不同的頂點(diǎn)u和v滿足|c(u)-c(v)|+D(u,v)≥n-1，其中D(u,v)表示G中u到v的最長(zhǎng)路徑的長(zhǎng)度。對(duì)一個(gè)Hamiltonian染色c，將max{c(u):u∈V(G)}稱為c的值，記作hc(c)。將min{hc(c):c是G的任意Hamiltonian染色}稱為G的Hamiltonian色數(shù)，記作hc(G)。如果G的一個(gè)Hamiltonian染色c滿足hc(c)=hc(G)，則稱c為G的最小的Hamiltonian染色。

1 預(yù)備知識(shí)

1.1 兩類特殊樹圖的概念

似星樹以及d-重似星樹的定義由文獻(xiàn)[8]提出，文獻(xiàn)[8]中限定了d≥3。筆者從另一角度(在似星樹的定義中允許d=2)給出相應(yīng)的概念，并引入標(biāo)準(zhǔn)似星樹及標(biāo)準(zhǔn)d-重似星樹的概念。

定義1 將一個(gè)頂點(diǎn)u0與d(d≥2)條長(zhǎng)度分別為mi(mi≥1,i=1,2,…,d)的路Pi的一個(gè)端頂點(diǎn)連一條邊，所得到的樹圖稱為似星樹(或稱為廣義星)，記作S(u0:m1,m2,…,md)，并稱u0為該似星樹的根(或稱為星心)，稱路Pi(i=1,2,…,d) ()為似星樹的懸掛路。特別地，若對(duì)任意的i=1,2,…,d，均有mi=m，則稱該似星樹為標(biāo)準(zhǔn)似星樹，記作S(u0:m(d))。

定義2 設(shè)似星樹S0(u0:m1,m2,…,md)的根u0的度d≥3，在其第i(i=1,2,…,d)條懸掛路的1度頂點(diǎn)與一個(gè)似星樹Si(ui:m1,…,mi-1,mi+1,…,md)的根ui粘連所得到的樹圖稱為d-重似星樹，記作S(S0(u0):m1,m2,…,md)。特別地，若對(duì)任意的i=1,2,…,d，均有mi=m，即S0(u0:m1,m2,…,md)是標(biāo)準(zhǔn)似星樹S(u0:m(d))，則稱相應(yīng)的d-重似星樹為標(biāo)準(zhǔn)d-重似星樹，記作S(S0(u0):m(d))。

1.2 一些引理

對(duì)于圖G的一個(gè)給定的頂點(diǎn)序列σ:v1,v2,…,vn，定義G的頂點(diǎn)集V(G)到正整數(shù)集的一個(gè)映射cσ：

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

(1)

關(guān)于似星樹，建立如下引理。

引理2 在一個(gè)似星樹G=S(x;l1,l2,…,lp)中，如果

(2)

則在G-x中存在一個(gè)頂點(diǎn)序列σ0，使σ0中任意個(gè)相鄰頂點(diǎn)不在G的同一懸掛路上。

證明 記G的第i(i=1,2,…,p)條懸掛路上的頂點(diǎn)為xi1,xi2,…,xili。下面對(duì)G中懸掛路個(gè)數(shù)p用數(shù)學(xué)歸納法來證明。

當(dāng)l1=l2時(shí)，在G-x中存在一個(gè)頂點(diǎn)序列σ0:x1l1,x2l2;x1(l1-1),x2(l2-1); …;x11,x21，使得σ0中任意個(gè)相鄰頂點(diǎn)不在G的同一懸掛路上。

當(dāng)l1=l2+1時(shí)，在G-x中存在一個(gè)頂點(diǎn)序列σ0:x1l1,x2l2;x1(l1-1),x2(l2-1); …;x12,x21;x11，使得σ0中任意2個(gè)相鄰頂點(diǎn)不在G的同一懸掛路上。

令p≥3，假設(shè)引理2的結(jié)論在似星樹的懸掛路個(gè)數(shù)p=n-1時(shí)成立。當(dāng)p=n時(shí)，不妨設(shè)l1≥ln≥…≥ln≥1。如果G是標(biāo)準(zhǔn)的似星樹，即l1=l2=…,=ln，則顯然在G-x中存在一個(gè)頂點(diǎn)序列σ0:x1l1,x2l2,…,xnln;x1(l1-1),x2(l2-1),…,xn(ln-1); …;x11,x21,…,xn1，使得σ0中任意2個(gè)相鄰頂點(diǎn)不在G的同一懸掛路上。否則，一定有l(wèi)1-ln≥1。此時(shí)，可以經(jīng)ln步如下遞歸地構(gòu)造均滿足引理2條件(2)的ln個(gè)似星樹G(i)，i=1,2,…,ln。

斷言G(1)滿足引理2與之相應(yīng)的條件(2)式。

2 d-重似星樹的Hamiltonian色數(shù)

斷言1 對(duì)于G的任意頂點(diǎn)序列σ:v1,v2,…,vn，有

且上式等號(hào)成立當(dāng)且僅當(dāng)u0∈V(Pi,i+1)(i=1,2,…,n-1)，其中Pi,i+1表示從vi到vi+1的路。

事實(shí)上，由G的結(jié)構(gòu)可知，對(duì)任意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)

且上式等號(hào)成立當(dāng)且僅當(dāng)u0∈V(Pi,i+1)(i=1,2,…,n-1)。因此，斷言1成立。

斷言2 存在G的一個(gè)頂點(diǎn)序列σ*:v1,v2,…,vn，滿足v1=u0，vn∈N(u0)且u0∈V(Pi,i+1)(i=1,2,…,n-1)，其中Pi,i+1表示從vi到vi+1的路，使

事實(shí)上，據(jù)斷言1，如果G的一個(gè)頂點(diǎn)序列σ:v1,v2,…,vn滿足u0∈V(Pi,i+1)(i=1,2,…,n-1)，并且D(v1,u0)+D(vn,u0)達(dá)到它的最小值，那么D(σ)=D(G)。顯然，對(duì)G的任意一個(gè)頂點(diǎn)序列σ:v1,v2,…,vn，有D(v1,u0)+D(vn,u0)≥1，并且對(duì)于G的滿足v1=u0，vn∈N(u0)且u0∈V(Pi,i+1)(i=1,2,…,n-1)的每一個(gè)頂點(diǎn)序列σ*: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 對(duì)標(biāo)準(zhǔn)d-重似星樹G=S(S0(u0):m(d))，有

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

證明 根據(jù)標(biāo)準(zhǔn)d-重似星樹的定義，在定理1中對(duì)任意的i=1,2,…,d，令mi=m，即得推論1的結(jié)論。

3 非齊次廣義雙星的Hamiltonian色數(shù)

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

斷言3 對(duì)于G的任意頂點(diǎn)序列σ:v1,v2,…,vn，有

上式等號(hào)成立當(dāng)且僅當(dāng)x∈V(Pi,i+1)(i=1,2,…,n-1)，其中Pi,i+1表示從vi到vi+1的路。

事實(shí)上，對(duì)任意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)，因此

且上式等號(hào)成立當(dāng)且僅當(dāng)x∈V(Pi,i+1)(i=1,2,…,n-1)。因此，斷言3成立。

斷言4 存在G的一個(gè)頂點(diǎn)序列σ*:v1,v2,…,vn，滿足v1=x，vn∈N(x)且x∈V(Pi,i+1)(i=1,2,…,n-1)，其中Pi,i+1表示從vi到vi+1的路，使得

事實(shí)上，據(jù)斷言3，如果G的一個(gè)頂點(diǎn)序列σ:v1,v2,…,vn滿足x∈V(Pi,i+1)(i=1,2,…,n-1)，并且D(v1,x)+D(vn,x)達(dá)到它的最小值，那么D(σ)=D(G)。顯然，對(duì)G的任意一個(gè)頂點(diǎn)序列σ:v1,v2,…,vn，有D(v1,x)+D(vn,x)≥1，并且對(duì)于G的滿足v1=x,vn∈N(x)且x∈V(Pi,i+1)(i=1,2,…,n-1)的每一個(gè)頂點(diǎn)序列σ*:v1,v2,…,vn，有D(v1,x)+D(vn,x)=1。

當(dāng)t=0時(shí)，有|Vx|=|Vy|。易于發(fā)現(xiàn)存在G的一個(gè)頂點(diǎn)序列σ*: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時(shí)，總存在G的一個(gè)頂點(diǎn)序列σ*: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 對(duì)齊次廣義雙星G=S2(x:l(p);y:l(q))，有

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

證明 根據(jù)齊次廣義雙星的定義，在定理2中對(duì)任意的i=1,2,…,p，j=1,2,…,q，令li=mj=l，即得推論2的結(jié)論。

[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.現(xiàn)代圖論[M].北京：科學(xué)出版社,2001.

(責(zé)任編輯：朱寶昌)

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

河北省自然科學(xué)基金項(xiàng)目(項(xiàng)目編號(hào)：A2015407063)；秦皇島市科學(xué)技術(shù)研究與發(fā)展計(jì)劃項(xiàng)目(項(xiàng)目編號(hào)：201401A038)，河北科技師范學(xué)資助計(jì)劃項(xiàng)目(項(xiàng)目編號(hào)：CXTD2012-08；2013YB008)。

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

O157.5

A

1672-7983(2015)02-0001-06

申玉發(fā)(1965-)，教授，博士。主要研究方向：圖論與網(wǎng)絡(luò)最優(yōu)化。