Three infinite families of Hamilton-connected convex polytopes and their detour index

Sakander Hayat; Bagus Imanda; Asad Khan; Mohammed J. F. Alenazi; Sakander Hayat; Bagus Imanda; Asad Khan; Mohammed J. F. Alenazi

doi:10.3934/math.2025559

AIMS Mathematics

2025, Volume 10, Issue 5: 12343-12387. doi: 10.3934/math.2025559

Previous Article Next Article

Research article Special Issues

Three infinite families of Hamilton-connected convex polytopes and their detour index

1.
Mathematical Sciences, Faculty of Science, Univeriti Brunei Darussalam, Jln Tungku Link, Gadong BE1410, Brunei Darussalam
2.
Metaverse Research Institute, School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou, Guangdong 510006, China
3.
Department of Computer Engineering, College of Computer and Information Sciences (CCIS), King Saud University, Riyadh 11451, Saudi Arabia

Received: 22 October 2024 Revised: 18 March 2025 Accepted: 25 March 2025 Published: 27 May 2025
MSC : 05C38, 05C40, 05C45, 05C90

A path in a graph encompassing its whole vertex set is called Hamiltonian. Such a path with sharing the same initial and terminal vertices is called a Hamiltonian cycle. A graph comprising a Hamiltonian path (resp. cycle) is said to be traceable (resp. Hamiltonian). Graphs possessing Hamiltonian paths between every pair of their vertices are said to be Hamilton-connected. The computational complexity of evaluating a graph to be Hamilton-connected is NP-complete. A detour is the longest path in a graph. The detour index is the sum of the length of detours between every unordered pair of vertices. Computing the detour index of a graph is an NP-complete problem as well. A finite subset $ P\subset \mathbb{R}^ \varepsilon $ is called a convex polytope if $ P $ is a convex hull. In this paper, we devised two distinct methods to prove a graph to be Hamilton-connected and employed these methods to construct some infinite families of Hamilton-connected convex polytopes. The convex polytope $ B_ \varepsilon $ has been shown to be non-Hamilton-connected in the literature. We showed that the existing proof for $ B_ \varepsilon $ is false and showed that this family is, in fact, Hamilton-connected. The paper is concluded with study implications followed by some future directions.
- graph,
- Hamiltonian path,
- Hamiltonian cycle,
- Hamilton-connected graph,
- detour index,
- NP-complete problems,
- convex polytopes
Citation: Sakander Hayat, Bagus Imanda, Asad Khan, Mohammed J. F. Alenazi. Three infinite families of Hamilton-connected convex polytopes and their detour index[J]. AIMS Mathematics, 2025, 10(5): 12343-12387. doi: 10.3934/math.2025559

Related Papers:

Abstract

A path in a graph encompassing its whole vertex set is called Hamiltonian. Such a path with sharing the same initial and terminal vertices is called a Hamiltonian cycle. A graph comprising a Hamiltonian path (resp. cycle) is said to be traceable (resp. Hamiltonian). Graphs possessing Hamiltonian paths between every pair of their vertices are said to be Hamilton-connected. The computational complexity of evaluating a graph to be Hamilton-connected is NP-complete. A detour is the longest path in a graph. The detour index is the sum of the length of detours between every unordered pair of vertices. Computing the detour index of a graph is an NP-complete problem as well. A finite subset $ P\subset \mathbb{R}^ \varepsilon $ is called a convex polytope if $ P $ is a convex hull. In this paper, we devised two distinct methods to prove a graph to be Hamilton-connected and employed these methods to construct some infinite families of Hamilton-connected convex polytopes. The convex polytope $ B_ \varepsilon $ has been shown to be non-Hamilton-connected in the literature. We showed that the existing proof for $ B_ \varepsilon $ is false and showed that this family is, in fact, Hamilton-connected. The paper is concluded with study implications followed by some future directions.

References

[1]	B. Alspach, J. P. Liu, On the Hamilton connectivity of generalized Petersen graphs, Discrete Math., 309 (2009), 5461–5473. https://doi.org/10.1016/j.disc.2008.12.016 doi: 10.1016/j.disc.2008.12.016
[2]	M. Bača, Face anti-magic labelings of convex polytopes, Util. Math., 55 (1999), 221–226.
[3]	M. Bača, Labelings of two classes of convex polytopes, Util. Math., 34 (1988), 24–31.
[4]	M. Bača, On magic labellings of convex polytopes, Ann. Discrete Math., 51 (1992), 13–16. https://doi.org/10.1016/S0167-5060(08)70599-5 doi: 10.1016/S0167-5060(08)70599-5
[5]	L. W. Beineke, Characterizations of derived graphs, J. Combin. Theory, 9 (1970), 129–135. https://doi.org/10.1016/s0021-9800(70)80019-9 doi: 10.1016/s0021-9800(70)80019-9
[6]	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
[7]	G. Chartrand, A. M. Hobbs, H. A. Jung, S. F. Kapoor, C. S. J. A. Nash-Williams, The square of a block is Hamiltonian connected, J. Combin. Theory Ser. B, 16 (1974), 290–292. https://doi.org/10.1016/0095-8956(74)90075-6 doi: 10.1016/0095-8956(74)90075-6
[8]	A. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math., 66 (2001), 211–249. https://doi.org/10.1023/A:1010767517079 doi: 10.1023/A:1010767517079
[9]	R. Frucht, A canonical representation of trivalent Hamiltonian graphs, J. Graph Theory, 1 (1977), 45–60. https://doi.org/10.1002/jgt.3190010111 doi: 10.1002/jgt.3190010111
[10]	F. V. Fomin, P. A. Golovach, W. Lochet, D. Sagunov, S. Saurabh, K. Simonov, Detours in directed graphs, J. Comput. Syst. Sci., 137 (2023), 66–86. https://doi.org/10.1016/j.jcss.2023.05.001
[11]	M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, San Francisco: W. H. Freeman and Company, 1983.
[12]	V. S. Gordon, Y. L. Orlovich, F. Werner, Hamiltonian properties of triangular grid graphs, Discrete Math., 308 (2008), 6166–6188. https://doi.org/10.1016/j.disc.2007.11.040 doi: 10.1016/j.disc.2007.11.040
[13]	Y. G. 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
[14]	F. Harary, Graph theory, Addison-Wesley, 1969.
[15]	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
[16]	R. W. Hung, F. Keshavarz-Kohjerdi, C. B. Lin, J. S. Chen, The Hamiltonian connectivity of alphabet supergrid graphs, IAENG Int. J. Appl. Math., 49 (2019), 1–17.
[17]	M. Imran, H. M. A. Siddiqui, Computing the metric dimension of convex polytopes generated by wheel related graphs, Acta Math. Hungar., 149 (2016), 10–30. https://doi.org/10.1007/s10474-016-0606-1 doi: 10.1007/s10474-016-0606-1
[18]	Z. Kewen, H. J. Lai, J. Zhou, Hamiltonian-connected graphs, Comput. Math. Appl., 55 (2008), 2707–2714. https://doi.org/10.1016/j.camwa.2007.10.018
[19]	R. Kužel, L. Xiong, Every 4-connected line graph is Hamiltonian if and only if it is Hamiltonian connected, In: Hamiltonian properties of graphs, Ph.D. thesis, U.W.B. Pilsen, 2004.
[20]	I. Lukovits, Indicators for atoms included in cycles, J. Chem. Inf. Comput. Sci., 36 (1996), 65–68. https://doi.org/10.1021/ci950082o doi: 10.1021/ci950082o
[21]	I. Lukovits, The detour index, Croat. Chem. Acta, 69 (1996), 873–882.
[22]	I. Lukovits, M. Razinger, On calculation of the detour index, J. Chem. Inf. Comput. Sci., 37 (1997), 283–286. https://doi.org/10.1021/ci960034j doi: 10.1021/ci960034j
[23]	J. B. Liu, X. Wang, J. D. Cao, The coherence and properties analysis of balanced $2^p$-ary tree networks, IEEE Trans. Netw. Sci. Eng., 11 (2024), 4719–4728. https://doi.org/10.1109/TNSE.2024.3395710 doi: 10.1109/TNSE.2024.3395710
[24]	O. Ore, Hamilton-connected graphs, J. Math. Pure Appl., 42 (1963), 21–27.
[25]	G. Rücker, C. Rücker, Symmetry-aided computation of the detour matrix and the detour index, J. Chem. Inf. Comput. Sci., 38 (1998), 710–714. https://doi.org/10.1021/ci980024d doi: 10.1021/ci980024d
[26]	H. Raza, S. Hayat, X. F. Pan, Binary locating-dominating sets in rotationally-symmetric convex polytopes, Symmetry, 10 (2018), 1–18. https://doi.org/10.3390/sym10120727 doi: 10.3390/sym10120727
[27]	H. Raza, S. Hayat, X. F. Pan, On the fault-tolerant metric dimension of convex polytopes, Appl. Math. Comput., 339 (2018), 172–185. https://doi.org/10.1016/j.amc.2018.07.010 doi: 10.1016/j.amc.2018.07.010
[28]	H. Raza, J. B. Liu, S. J. Qu, On mixed metric dimension of rotationally symmetric graphs, IEEE Access, 8 (2020), 11560–11569. https://doi.org/10.1109/ACCESS.2019.2961191 doi: 10.1109/ACCESS.2019.2961191
[29]	A. Simić, M. Bogdanović, J. Milošević, The binary locating-dominating number of some convex polytopes, Ars Math. Contemp., 13 (2017), 367–377.
[30]	C. Thomassen, Hamiltonian-connected tournaments, J. Combin. Theory Ser. B, 28 (1980), 142–163. https://doi.org/10.1016/0095-8956(80)90061-1 doi: 10.1016/0095-8956(80)90061-1
[31]	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
[32]	N. Trinajstić, S. Nikolić, Z. Mihalić, On computing the molecular detour matrix, Int. J. Quantum Chem., 65 (1997), 415–419. https://doi.org/10.1002/(SICI)1097-461X(1997)65:5<415::AID-QUA6>3.0.CO;2-Z doi: 10.1002/(SICI)1097-461X(1997)65:5<415::AID-QUA6>3.0.CO;2-Z
[33]	N. Trinajstić, S. Nikolić, B. Lučić, D. Amić, Z. Mihalić, The detour matrix in chemistry, J. Chem. Inf. Comput. Sci., 37 (1997), 631–638. https://doi.org/10.1021/ci960149n doi: 10.1021/ci960149n
[34]	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
[35]	H. Whitney, Congruent graphs and the connectivity of graphs, In: Hassler Whitney collected papers, 1992, 61–79.
[36]	J. Wei, Z. F. You, H. J. Lai, Spectral analogues of Erdös' theorem on Hamilton-connected graphs, Appl. Math. Comput., 340 (2019), 242–250. https://doi.org/10.1016/j.amc.2018.08.005 doi: 10.1016/j.amc.2018.08.005
[37]	X. J. Yang, J. F. Du, L. M. Xiong, Forbidden subgraphs for supereulerian and Hamiltonian graphs, Discrete Appl. Math., 288 (2021), 192–200. https://doi.org/10.1016/j.dam.2020.08.034 doi: 10.1016/j.dam.2020.08.034
[38]	X. F. Yang, D. J. Evans, H. J. Lai, G. M. Megson, Generalized honeycomb torus is Hamiltonian, Inform. Process. Lett., 92 (2004), 31–37. https://doi.org/10.1016/j.ipl.2004.05.017 doi: 10.1016/j.ipl.2004.05.017
[39]	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
[40]	Q. N. Zhou, L. G. Wang, Some sufficient spectral conditions on Hamilton-connected and traceable graphs, Linear Multilinear Algebra, 65 (2017), 224–234. https://doi.org/10.1080/03081087.2016.1182463 doi: 10.1080/03081087.2016.1182463
[41]	Q. N. Zhou, L. G. Wang, Y. Lu, Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree, Linear Algebra Appl., 592 (2020), 48–64. https://doi.org/10.1016/j.laa.2020.01.021 doi: 10.1016/j.laa.2020.01.021
[42]	Q. N. Zhou, L. G. Wang, Y. Lu, Wiener index and Harary index on Hamilton-connected graphs with large minimum degree, Discrete Appl. Math., 247 (2018), 180–185. https://doi.org/10.1016/j.dam.2018.03.063 doi: 10.1016/j.dam.2018.03.063

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)