On hamiltonian colorings of block graphs

A hamiltonian coloring c of a graph G of order p is an assignment of colors to the vertices of G such that $D(u,v)+\mathrm{\mid }c(u)-c(v)\mathrm{\mid }\ge p-1$ for every two distinct vertices u and v of G, where D(u,v) denoted the detour distance between u and v. The value hc© of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number, denoted by hc(G), is the min{hc©} taken over all hamiltonian coloring c of G. In this paper, we present a lower bound for the hamiltonian chromatic number of block graphs and give a sufficient condition to achieve the lower bound. We characterize symmetric block graphs achieving this lower bound. We present two algorithms for optimal hamiltonian coloring of symmetric block graphs.