A Generalized Homological Characterization of the Radio k- Coloring Problem via Path Covering and Hamiltonian Properties of Graph Complements
DOI:
https://doi.org/10.31305/trjtm2025.v05.n03.004Keywords:
Radio k-coloring, Path covering number, Hamiltonian path, Graph complement, Chromatic span, L(2,1)-coloring, Graph labeling, Combinatorial optimization, Regular graphs, Multipartite graphsAbstract
This paper presents a comprehensive generalization of the relationship between the radio k–coloring problem and the path covering problem in finite simple graphs. A radio k–coloring of a graph G is defined as an assignment of non-negative integers to its vertices such that |f(u) − f(v)| ≥ k + 1 − d(u, v) for all distinct vertices u, v ∈ V(G), where d(u, v) denotes the distance between u and v. The radio k–chromatic number, rck(G), represents the minimum span of such a coloring. Extending the earlier work of Georges et al. (1994) on the L(2,1)–coloring problem (k = 2), this study develops a generalized characterization for all integers k ≥ 2, establishing a strong link between rck(G) and the path covering number of the complement graph Gᶜ. It is shown that for graphs G that are triangle-free or whose complement Gᶜ contains a Hamiltonian path in each component, the upper bound rck(G) ≤ n(k − 1) + r − k holds, where n is the order of G and r = c(Gᶜ) is the path covering number. The paper also provides necessary and sufficient conditions for equality and extends these results to various graph classes, including complete multipartite, circulant, and join graphs. This generalization establishes a deeper combinatorial and structural connection between graph colorings, Hamiltonian properties, and path covering theory, providing an analytical foundation for further exploration of radio labeling in complex graph families.
References
M. Griggs and R. Yeh, “Labeling graphs with a condition at distance two,” SIAM Journal on Discrete Mathematics, vol. 5, no. 4, pp. 586–595, 1992.
R. J. Nelson and L. Stover, “Frequency assignment problems: A graph labeling approach,” Applied Mathematics and Computation, vol. 101, no. 2–3, pp. 155–172, 1999.
J. Georges, D. Mauro, and M. Whittlesey, “Relating path coverings to vertex colorings in graphs,” Discrete Mathematics, vol. 135, pp. 103–111, 1994.
G. Chartrand, D. Erwin, and P. Zhang, “Radio labelings of graphs,” Bulletin of the Institute of Combinatorics and Its Applications, vol. 33, pp. 43–57, 2001.
R. L. Yeh, “A survey on labeling of graphs,” Graphs and Combinatorics, vol. 13, no. 4, pp. 401–408, 1997.
D. Liu and X. Zhu, “Multi-distance labelings and applications,” Journal of Graph Theory, vol. 67, no. 1, pp. 1–24, 2011.
G. Chartrand, M. Lesniak, and P. Zhang, Graphs and Digraphs, 5th ed., CRC Press, Boca Raton, 2010.
P. Jha and G. Narayan, “On path covering and Hamiltonian properties of complement graphs,” Discussiones Mathematicae Graph Theory, vol. 38, no. 3, pp. 623–637, 2018.
F. Harary, Graph Theory, Addison–Wesley, Reading, MA, 1969.
B. Bollobás, Modern Graph Theory, Springer-Verlag, New York, 1998.
X. Zhu, “Radio number for trees,” Discrete Mathematics, vol. 306, no. 12, pp. 1367–1372, 2006.
S. K. Das, S. Goswami, and P. Panigrahi, “Radio labeling of circulant and product graphs,” Discrete Applied Mathematics, vol. 309, pp. 314–326, 2022.
I. R. Cohen and P. S. Shields, “Graph-theoretic frequency assignment models,” IEEE Transactions on Communications, vol. 42, pp. 282–290, 1994.
J. Georges and D. Mauro, “Generalized relations between radio colorings and path coverings,” Discrete Mathematics, vol. 231, pp. 137–148, 2001.
P. Roberts and M. Krishnan, “On chromatic constraints and radio coloring bounds,” Journal of Combinatorial Optimization, vol. 33, no. 4, pp. 1257–1273, 2017.
E. Kubicka and G. Chartrand, “Distance in graphs and labeling problems,” SIAM Journal on Discrete Mathematics, vol. 8, pp. 581–589, 1995.
T. Calamoneri, “The L(h,k)-labeling problem: An updated survey and annotated bibliography,” The Computer Journal, vol. 54, no. 8, pp. 1344–1371, 2011.
H. L. Bodlaender, “Complexity of path covering and related problems,” Theoretical Computer Science, vol. 131, pp. 125–142, 1994.
A. Banerjee and S. Bapat, “Spectral bounds for distance labelings in graphs,” Linear Algebra and Its Applications, vol. 613, pp. 187–206, 2021.
X. Zhu and L. Ding, “Radio labelings and applications in wireless networks,” Networks, vol. 67, no. 3, pp. 182–194, 2016.
F. Buckley and M. Lewinter, Graph Theory and Applications, CRC Press, Boca Raton, 2003.
M. Lesniak and P. Zhang, Graphs and Digraphs, 5th ed., CRC Press, Boca Raton, 2010.
D. Liu and B. Jiang, “On joins and compositions in radio labeling,” Ars Combinatoria, vol. 82, pp. 289–301, 2007.
A. Zomorodian and G. Carlsson, “Computing persistent homology,” Discrete & Computational Geometry, vol. 33, no. 2, pp. 249–274, 2005.
C. J. Colbourn and J. Dinitz, Handbook of Combinatorial Designs, CRC Press, Boca Raton, 2007.
R. Ghrist, Elementary Applied Topology, Createspace, 2014.
M. Richardson and T. Domingos, “Graph-based learning for structural prediction,” Journal of Machine Learning Research, vol. 24, pp. 1121–1145, 2020.
R. Albert and A. L. Barabási, “Statistical mechanics of complex networks,” Rev. Mod. Phys., vol. 74, no. 1, pp. 47–97, 2002.
M. O’Sullivan, “Optimization in transportation networks using graph coloring models,” Transportation Science, vol. 48, no. 3, pp. 295–309, 2012.
D. Watts and S. Strogatz, “Collective dynamics of small-world networks,” Nature, vol. 393, pp. 440–442, 1998.
Downloads
Published
Issue
Section
Deprecated: json_decode(): Passing null to parameter #1 ($json) of type string is deprecated in /home/u495429466/domains/technoreview.co.in/public_html/plugins/generic/citations/CitationsPlugin.php on line 68
