两类树图的Hamiltonian色数

Hamiltonian Chromatic Number for Two Classes of Tree Graphs

一个n阶连通图G的Hamiltonian染色是从G的顶点集V(G)到正整数集N(称为颜色集)的一个映射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),u≠v}≤n/2的d-重似星树和广义双星这两类树图的Hamiltonian色数的确切值。

A Hamiltonian coloring of a connected graph G of order n is an assignment c of colors （ positive in-tegers） to the vertices of G such thatc（u）-c（v）｜＋D（u,v）≥n-1for every two distinct vertices u and v of G, where D（u,v） is the length of a longest u -v path in G. For an Hamiltonian coloring c, the value of is c, denoted by hc（ c）, while the Hamiltonian chromatic number of G is rain I hc（c） ：c is taken over all humiltonian colorings of G} , denoted by hc（G）. In this paper, we obtain the exact values of Hamiltonian chromatic num-ber for d-starlike trees and generalized double stars, as two classes of tree graphs.