完全正则m-元树的Hamiltonian色数与最小Hamiltonian着色
|
摘要
对一个n阶连通图G,G的Hamiltonian着色(以下简称G的H着色)定义为从G的顶点集V(G)到正整数集N(称为颜色集)的一个映射c,且对G的任意2个不同顶点u和v,满足|c(u)-c(v)|+D(u,v)≥n-1,其中D(u,v)表示G中u到v的最长路径的长度。对G的一个H着色c,将Max{c(u)|u∈V(G)}称为c的值,记作hc(c)。将Min{hc(c)|c是G的H着色}称为G的Hamiltonian色数(以下简称G的H色数),记作hc(G)。如果G的一个H着色c满足hc(c)=hc(G),则称c为G的一个最小H着色。本次研究得到了完全正则m-元树的H色数的确切值,并给出了其最小H着色。
For a connected graph of G order n, a Hamiltonian coloring of G(named a H coloring of G for short) is a mapping c from a set of vertices of G to a set of positive integers V(G)→{1,2,3,…}(called a color set). And for every two distinct vertices u and v of G, the formula |c(u)-c(v)|+D(u,v)≥n-1 will be satisfied, in whih D(u,v) is the length of a longest u-v path in G. The Hamiltonian chromatic number hc(G) of G(named the H chromatic number hc(G) of G for short) is Min{hc(c)} taken over all H coloring c of G. A H coloring c of G is a minimum H coloring if hc(c)=hc(G). The exact values of H chromatic number for the completely regular m-ary trees are obtained, and a minimum H coloring for them is presented.
For a connected graph of G order n, a Hamiltonian coloring of G(named a H coloring of G for short) is a mapping c from a set of vertices of G to a set of positive integers V(G)→{1,2,3,…}(called a color set). And for every two distinct vertices u and v of G, the formula |c(u)-c(v)|+D(u,v)≥n-1 will be satisfied, in whih D(u,v) is the length of a longest u-v path in G. The Hamiltonian chromatic number hc(G) of G(named the H chromatic number hc(G) of G for short) is Min{hc(c)} taken over all H coloring c of G. A H coloring c of G is a minimum H coloring if hc(c)=hc(G). The exact values of H chromatic number for the completely regular m-ary trees are obtained, and a minimum H coloring for them is presented.
引文
[1] Chartrand G,Nebesky L,Zhang P.Hamiltonian Colorings of Graphs[J].Discrete Applied Mathematics,2005,146(3):257-272.
[2] Chartrand G,Nebesky L,Zhang P.On Hamiltonian Colorings of Graphs[J].Discrete Mathematics,2005,290(2):133-143.
[3] Chartrand G,Nebesky L,Zhang P.A Survey of Hamiltonian Colorings of Graphs[J].Congressus Numerantium,2004,169:179-192.
[4] Khennoufa R,Tongi O.A Note on Radio Antipodal Colourings of Paths[J].Math Bohem,2005,130:277-282.
[5] Shen Yufa,He Wenjie,Li Xue,et al.On Hamiltonian Colorings for Some Graphs[J].Discrete Applied Mathematics,2008,156(15):3 028-3 034.
[6] 申玉发,高烨,王莹,等.两类树图的Hamiltonian色数[J].河北科技师范学院学报,2015,29(2):1-6.
[7] 龚劬.图论与网络最优化算法[M].重庆:重庆大学出版社,2009.
[8] Li Xiangwen,Mak Vicky,Zhou Sanming.Optimal Radio Labeling of Complete m-ary Trees[J].Discrete Applied Mathematics,2010,158(5):507-515.
[2] Chartrand G,Nebesky L,Zhang P.On Hamiltonian Colorings of Graphs[J].Discrete Mathematics,2005,290(2):133-143.
[3] Chartrand G,Nebesky L,Zhang P.A Survey of Hamiltonian Colorings of Graphs[J].Congressus Numerantium,2004,169:179-192.
[4] Khennoufa R,Tongi O.A Note on Radio Antipodal Colourings of Paths[J].Math Bohem,2005,130:277-282.
[5] Shen Yufa,He Wenjie,Li Xue,et al.On Hamiltonian Colorings for Some Graphs[J].Discrete Applied Mathematics,2008,156(15):3 028-3 034.
[6] 申玉发,高烨,王莹,等.两类树图的Hamiltonian色数[J].河北科技师范学院学报,2015,29(2):1-6.
[7] 龚劬.图论与网络最优化算法[M].重庆:重庆大学出版社,2009.
[8] Li Xiangwen,Mak Vicky,Zhou Sanming.Optimal Radio Labeling of Complete m-ary Trees[J].Discrete Applied Mathematics,2010,158(5):507-515.