Hamiltonian chromatic number of trees
share
Let G be a simple finite connected graph of order n. The detour distance between two distinct vertices u and v denoted by D(u,v) is the length of a longest uv-path in G. A hamiltonian coloring h of a graph G of order n is a mapping h : V(G) →{0,1,2,...} such that D(u,v) + |h(u)-h(v)| ≥ n-1, for every two distinct vertices u and v of G. The span of h, denoted by span(h), is max{|h(u)-h(v)| : u, v ∈ V(G)}. The hamiltonian chromatic number of G is defined as hc(G) := min{span(h)} with minimum taken over all hamiltonian coloring h of G. In this paper, we give an improved lower bound for the hamiltonian chromatic number of trees and give a necessary and sufficient condition to achieve the improved lower bound. Using this result, we determine the hamiltonian chromatic number of two families of trees.
READ FULL TEXT