Hamiltonian chromatic number of block graphs
share
Let G be a simple connected graph of order n. A hamiltonian coloring c of a graph G is an assignment of colors (non-negative integers) to the vertices of G such that D(u, v) + |c(u) - c(v)| ≥ n - 1 for every two distinct vertices u and v of G, where D(u, v) denotes the detour distance between u and v in G which is the length of the longest path between u and v. The value hc(c) of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number, denoted by hc(G), is min{hc(c)} taken over all hamiltonian coloring c of G. In this paper, we give a necessary and sufficient condition to achieve a lower bound for the hamiltonian chromatic number of block graphs given in [Theorem 1,On Hamiltonian Colorings of Block graphs, In: Kaykobad, M., Petrechi, R., (eds.) WALCOM: Algorithms and Computation, LNCS: 9627, 28-39, 2016]. We present an algorithm for optimal hamiltonian coloring of a special class of block graphs, namely SDB(p/2) block graphs. We characterize level-wise regular block graphs and extended star of blocks achieving this lower bound.
READ FULL TEXT