Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016)
DOI: 10.7155/jgaa.00420
Hamiltonian chromatic number of block graphs
Devsi Bantva
Vol. 21, no. 3, pp. 353-369, 2017. Regular paper.
Abstract 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)|$ $\geq$ $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 [Bantva, WALCOM 2016. Theorem 1]. 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.
Submitted: May 2016.
Reviewed: November 2016.
Revised: December 2016.
Reviewed: December 2016.
Revised: December 2016.
Accepted: December 2016.
Final: January 2017.
Published: February 2017.
Communicated by Mohammed Kaykobad and Rossella Petreschi
article (PDF)
BibTeX