Abstract
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) + \(|c(u) - c(v)|\) \(\ge \) \(p - 1\) for every two distinct vertices u and v of G, where D(u, v) denotes the detour distance 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 the min{hc(c)} 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bantva, D.: On hamiltonian colorings of trees, communicated
Chartrand, G., Nebeský, L., Zhang, P.: Hamiltonian coloring of graphs. Discrete Appl. Math. 146, 257–272 (2005)
Chartrand, G., Nebeský, L., Zhang, P.: On hamiltonian colorings of graphs. Discrete Math. 290, 133–143 (2005)
Chartrand, G., Escuadro, H., Zhang, P.: Detour distance in graphs. J. Combin. Math. Combin. Comput. 53, 75–94 (2005)
Khennoufa, R., Togni, O.: A note on radio antipodal colourings of paths. Math. Bohemica 130(3), 277–282 (2005)
Shen, Y., He, W., Li, X., He, D., Yang, X.: On hamiltonian colorings for some graphs. Discrete Appl. Math. 156, 3028–3034 (2008)
Vaidya, S.K., Bantva, D.D.: Symmetric regular cacti - properties and enumeration. Proyecciones J. Math. 31(3), 261–275 (2012)
West, D.B.: Introduction to Graph theory. Prentice-Hall of India, New Delhi (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Bantva, D. (2016). On Hamiltonian Colorings of Block Graphs. In: Kaykobad, M., Petreschi, R. (eds) WALCOM: Algorithms and Computation. WALCOM 2016. Lecture Notes in Computer Science(), vol 9627. Springer, Cham. https://doi.org/10.1007/978-3-319-30139-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-30139-6_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-30138-9
Online ISBN: 978-3-319-30139-6
eBook Packages: Computer ScienceComputer Science (R0)