Combinatorial analysis of line graphs: domination, chromaticity, and Hamiltoniancity

Yubin Zhong; Sakander Hayat; Suliman Khan; Vito Napolitano; Mohammed J. F. Alenazi; Yubin Zhong; Sakander Hayat; Suliman Khan; Vito Napolitano; Mohammed J. F. Alenazi

doi:10.3934/math.2025599

AIMS Mathematics

2025, Volume 10, Issue 6: 13343-13364. doi: 10.3934/math.2025599

Previous Article Next Article

Research article Special Issues

Combinatorial analysis of line graphs: domination, chromaticity, and Hamiltoniancity

1.
School of Mathematics and Information Sciences, Guangzhou University, Guangzhou, Guangdong 510006, China
2.
Mathematical Sciences, Faculty of Science, Universiti Brunei Darussalam, Jalan Tungku Link, Gadong BE1410, Brunei Darussalam
3.
Department of Mathematics and Physics, University of Campania "Luigi Vanvitelli", Viale Lincoln 5, Caserta, I-81100, Italy
4.
Department of Computer Engineering, College of Computer and Information Sciences (CCIS), King Saud University, Riyadh 11451, Saudi Arabia

Received: 29 December 2024 Revised: 07 March 2025 Accepted: 25 March 2025 Published: 10 June 2025
MSC : 05C09, 05C25, 05C50

Line graphs are a fundamental class of graphs extensively studied for their structural properties and applications in diverse fields such as network design, optimization, and algorithm development. Pan and lollipop graphs, with their distinctive hybrid structures, offer a fertile ground for exploring combinatorial properties in their line graphs. Motivated by the need to better understand domination, chromaticity, and Hamiltonian properties in line graphs, this study examined the line graphs of pan and lollipop graphs. These investigations were inspired by their potential applications in connectivity analysis and optimization in networks. We derived analytical formulas for the domination and chromatic numbers of these line graphs, established relationships between these parameters and their corresponding original graphs, and proved that the line graph of a pan graph is Hamiltonian while that of a lollipop graph is traceable. The methodology combines established theoretical results and inequalities, including domination bounds and chromaticity relations, with rigorous combinatorial analysis. Our results not only contribute to the theoretical understanding of line graphs but also have implications for practical problems in network optimization and graph algorithm design, opening avenues for further research into hybrid graph structures.
- line graph,
- pan graph,
- lollipop graph,
- domination number,
- Hamiltoniancity,
- chromatic number,
- traceability
Citation: Yubin Zhong, Sakander Hayat, Suliman Khan, Vito Napolitano, Mohammed J. F. Alenazi. Combinatorial analysis of line graphs: domination, chromaticity, and Hamiltoniancity[J]. AIMS Mathematics, 2025, 10(6): 13343-13364. doi: 10.3934/math.2025599

Related Papers:

Abstract

Line graphs are a fundamental class of graphs extensively studied for their structural properties and applications in diverse fields such as network design, optimization, and algorithm development. Pan and lollipop graphs, with their distinctive hybrid structures, offer a fertile ground for exploring combinatorial properties in their line graphs. Motivated by the need to better understand domination, chromaticity, and Hamiltonian properties in line graphs, this study examined the line graphs of pan and lollipop graphs. These investigations were inspired by their potential applications in connectivity analysis and optimization in networks. We derived analytical formulas for the domination and chromatic numbers of these line graphs, established relationships between these parameters and their corresponding original graphs, and proved that the line graph of a pan graph is Hamiltonian while that of a lollipop graph is traceable. The methodology combines established theoretical results and inequalities, including domination bounds and chromaticity relations, with rigorous combinatorial analysis. Our results not only contribute to the theoretical understanding of line graphs but also have implications for practical problems in network optimization and graph algorithm design, opening avenues for further research into hybrid graph structures.

References

[1]	S. Alikhani, Y. H. Peng, K. A. M. Atan, On the domination number of some graphs, Int. Math. Forum, 3 (2008), 1879–1884.
[2]	C. Berge, The theory of graphs and its applications, London: Methuen, 1962.
[3]	C. Bujtás, Domination number of graphs with minimum degree five, Discuss. Math. Graph Theory, 41 (2021), 763–777. https://doi.org/10.7151/dmgt.2339 doi: 10.7151/dmgt.2339
[4]	R. A. Brualdi, R. F. Shanny, Hamiltonian line graphs, J. Graph Theory, 5 (1981), 307–314. https://doi.org/10.1002/jgt.3190050312 doi: 10.1002/jgt.3190050312
[5]	G. Chartrand, Introduction to graph theory, New Delhi: Tata McGraw-Hill Education, 2006.
[6]	L. Clark, On Hamiltonian line graphs, J. Graph Theory, 8 (1984), 303–307. https://doi.org/10.1002/jgt.3190080210 doi: 10.1002/jgt.3190080210
[7]	D. H. Cai, P. Z. Fan, Q. Y. Zou, Y. Q. Xu, Z. G. Ding, Z. Q. Liu, Active device detection and performance analysis of massive non-orthogonal transmissions in cellular Internet of Things, Sci. China Inform. Sci., 65 (2022), 182301. https://doi.org/10.1007/s11432-021-3328-y doi: 10.1007/s11432-021-3328-y
[8]	G. Chartrand, P. Zhang, A first course in graph theory, Courier Corporation, 2013.
[9]	D. Duffus, B. Sands, R. E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory, 9 (1985), 487–495. https://doi.org/10.1002/jgt.3190090409 doi: 10.1002/jgt.3190090409
[10]	W. Goddard, M. A. Henning, Domination in planar graphs with small diameter, J. Graph Theory, 40 (2002), 1–25. https://doi.org/10.1002/jgt.10027 doi: 10.1002/jgt.10027
[11]	Y. H. Guo, R. Zhao, S. W. Lai, L. S. Fan, X. F. Lei, G. K. Karagiannidis, Distributed machine learning for multiuser mobile edge computing systems, IEEE J. Sel. Top. Signal Process., 16 (2022), 460–473. https://doi.org/10.1109/jstsp.2022.3140660 doi: 10.1109/jstsp.2022.3140660
[12]	T. W. Haynes, M. A. Henning, The domatic numbers of factors of graphs, Ars Combin., 56 (2000), 161–173.
[13]	T. W. Haynes, S. Hedetniemi, P. Slater, Fundamentals of domination in graphs, New York: Marcel Dekker, 1998.
[14]	S. Hayat, A. Khan, S. Khan, J. B. Liu, Hamilton connectivity of convex polytopes with applications to their detour index, Complexity, 2021 (2021), 6684784. https://doi.org/10.1155/2021/6684784 doi: 10.1155/2021/6684784
[15]	F. Harary, C. S. J. A. Nash-Williams, On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull., 8 (1965), 701–709. https://doi.org/10.4153/cmb-1965-051-3 doi: 10.4153/cmb-1965-051-3
[16]	M. J. Jou, J. J. Lin, Domination numbers of trees, In: Proceedings of the 2017 International Conference on Applied Mathematics, Modelling and Statistics Application (AMMSA 2017), 319–321. https://doi.org/10.2991/ammsa-17.2017.71
[17]	C. X. Kang, On domination number and distance in graphs, Discrete Appl. Math., 200 (2016), 203–206. https://doi.org/10.1016/j.dam.2015.07.009 doi: 10.1016/j.dam.2015.07.009
[18]	S. Khan, S. Hayat, A. Khan, M. Y. H. Malik, J. D. Cao, Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications, AIMS Math., 6 (2021), 3947–3973. https://doi.org/10.3934/math.2021235 doi: 10.3934/math.2021235
[19]	J. B. Liu, Y. Bao, W. T. Zheng, Analyses of some structural properties on a class of hierarchical scale-free networks, Fractals, 30 (2022), 2250136. https://doi.org/10.1142/S0218348X22501365 doi: 10.1142/S0218348X22501365
[20]	J. B. Liu, Y. Bao, W. T. Zheng, S. Hayat, Network coherence analysis on a family of nested weighted $n$-polygon networks, Fractals, 29 (2021), 2150260. https://doi.org/10.1142/S0218348X21502601 doi: 10.1142/S0218348X21502601
[21]	J. B. Liu, C. X. Wang, S. H. Wang, B. Wei, Zagreb indices and multiplicative Zagreb indices of Eulerian graphs, Bull. Malays. Math. Sci. Soc., 42 (2019), 67–78. https://doi.org/10.1007/s40840-017-0463-2 doi: 10.1007/s40840-017-0463-2
[22]	G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory, 22 (1996), 213–229. https://doi.org/10.1002/(SICI)1097-0118(199607)22:3<213::AID-JGT2>3.0.CO;2-P doi: 10.1002/(SICI)1097-0118(199607)22:3<213::AID-JGT2>3.0.CO;2-P
[23]	O. Ore, Theory of graphs, American Mathematical Society, 1962.
[24]	H. Pahlings, On the chromatic number of skew graphs, J. Combin. Theory Ser. B, 25 (1978), 303–306. https://doi.org/10.1016/0095-8956(78)90006-0 doi: 10.1016/0095-8956(78)90006-0
[25]	G. Rajasekar, K. Nagarajan, Algorithm for finding location domination number of a graph connected by a bridge, Int. J. Pure Appl. Math., 118 (2018), 313–321.
[26]	I. A. Stewart, Sufficient conditions for Hamiltonicity in multiswapped networks, J. Parallel Distrib. Comput., 101 (2017), 17–26. https://doi.org/10.1016/j.jpdc.2016.10.015 doi: 10.1016/j.jpdc.2016.10.015
[27]	N. Siddiqui, M. James, Domination and chromatic number of pan graph and lollipop graph, Int. J. Tech. Innov. Mod. Eng. Sci., 4 (2021), 932–939.
[28]	C. Y. Tan, D. H. Cai, F. Fang, Z. G. Ding, P. Z. Fan, Federated unfolding learning for CSI feedback in distributed edge networks, IEEE Trans. Commun., 73 (2025), 410–424. https://doi.org/10.1109/tcomm.2024.3429170 doi: 10.1109/tcomm.2024.3429170
[29]	B. Wei, Hamiltonian paths and Hamiltonian connectivity in graphs, Discrete Math., 121 (1993), 223–228. https://doi.org/10.1016/0012-365x(93)90555-8 doi: 10.1016/0012-365x(93)90555-8
[30]	D. B. West, Introduction to graph theory, Upper Saddle River: Prentice Hall, 2001.
[31]	H. B. Walikar, B. D. Acharya, Domination critical graphs, Nat. Acad. Sci. Lett., 2 (1979), 70–72.
[32]	Y. B. Zhong, S. Hayat, A. Khan, Hamilton-connectivity of line graphs with application to their detour index, J. Appl. Math. Comput., 68 (2022), 1193–1226. https://doi.org/10.1007/s12190-021-01565-2 doi: 10.1007/s12190-021-01565-2
[33]	S. H. Zheng, C. Shen, X. Chen, Design and analysis of uplink and downlink communications for federated learning, IEEE J. Sel. Areas Commun., 39 (2021), 2150–2167. https://doi.org/10.1109/jsac.2020.3041388 doi: 10.1109/jsac.2020.3041388

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)