Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications

Suliman Khan; Sakander Hayat; Asad Khan; Muhammad Yasir Hayat Malik; Jinde Cao; Suliman Khan; Sakander Hayat; Asad Khan; Muhammad Yasir Hayat Malik; Jinde Cao

doi:10.3934/math.2021235

AIMS Mathematics

2021, Volume 6, Issue 4: 3947-3973. doi: 10.3934/math.2021235

Previous Article Next Article

Research article

Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications

1.
Faculty of Engineering Sciences, GIK Institute of Engineering Sciences and Technology, Topi, Swabi, KPK, 23460, Pakistan
2.
School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou, 510006, P. R. China
3.
Department of Mathematics, Govt. College University Faisalabad, 38000, Pakistan
4.
School of Mathematics, Southeast University, Nanjing 211189, China
5.
Yonsei Frontier Lab, Yonsei University, Seoul 03722, Korea
^†These authors contributed equally to this work.

Received: 23 December 2020 Accepted: 01 February 2021 Published: 03 February 2021
MSC : 05C45, 05C40, 05C90

In this paper, we have used two different proof techniques to show the Hamilton-connectedness of graphs. By using the vertex connectivity and Hamiltoniancity of graphs, we construct an infinite family of Hamilton-connected convex polytope line graphs whose underlying family of convex polytopes is not Hamilton-connected. By definition, we constructed two more infinite families of Hamilton-connected convex polytopes. As a by-product of our results, we compute exact values of the detour index of the families of Hamilton-connected convex polytopes. Finally, we classify the Platonic solids according to their Hamilton-connectedness and Hamilton-laceability properties.
- graph,
- Hamiltonian path,
- Hamiltonian cycle,
- Hamilton-connected graph,
- detour index,
- NP-complete problems,
- Platonic solids,
- convex polytopes
Citation: Suliman Khan, Sakander Hayat, Asad Khan, Muhammad Yasir Hayat Malik, Jinde Cao. Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications[J]. AIMS Mathematics, 2021, 6(4): 3947-3973. doi: 10.3934/math.2021235

Related Papers:

Abstract

In this paper, we have used two different proof techniques to show the Hamilton-connectedness of graphs. By using the vertex connectivity and Hamiltoniancity of graphs, we construct an infinite family of Hamilton-connected convex polytope line graphs whose underlying family of convex polytopes is not Hamilton-connected. By definition, we constructed two more infinite families of Hamilton-connected convex polytopes. As a by-product of our results, we compute exact values of the detour index of the families of Hamilton-connected convex polytopes. Finally, we classify the Platonic solids according to their Hamilton-connectedness and Hamilton-laceability properties.

References

[1]	B. R. Alspach, J. Liu, On the Hamilton-connectivity of generalized Petersen graphs, Discrete Math., 309 (2009), 5461–5473. 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. Discret. Math., 51 (1992), 13–16. doi: 10.1016/S0167-5060(08)70599-5
[5]	L. W. Beineke, Characterizations of derived graphs, J. Comb. Theory, 9 (1970), 129–135. doi: 10.1016/S0021-9800(70)80019-9
[6]	J. M. Chang, J. S. Yang, Y. L. Wang, Y. Chang, Panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs, Networks, 44 (2004), 302–310. doi: 10.1002/net.20039
[7]	G. Chartrand, A. M. Hobbs, H. A. Jung, S. F. Kapoor, C. S. J. Nash-Williams, The square of a block is Hamiltonian connected, J. Comb. Theory B, 16 (1974), 290–292. 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. doi: 10.1023/A:1010767517079
[9]	R. Frucht, A canonical representation of trivalent Hamiltonian graphs, J. Graph Theor., 1 (1976), 45–60.
[10]	M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, New York: W. H. Freeman, 1983.
[11]	V. S. Gordon, Y. L. Orlovich, F. Werner, Hamiltonian properties of triangular grid graphs, Discrete Math., 308 (2008), 6166–6188. doi: 10.1016/j.disc.2007.11.040
[12]	F. Harary, Graph theory, Addison-Wesley, 1969.
[13]	R. W. Hung, F. Keshavarz-Kohjerdi, C. B. Lin, J. S. Chen, The Hamiltonian connectivity of alphabet supergrid graphs, Int. J. Appl. Math., 49 (2019), 1–10.
[14]	M. Imran, H. M. A. Siddiqui, Computing the metric dimension of convex polytopes generated by wheel related graphs, Acta Math. Hung., 149 (2016), 10–30. doi: 10.1007/s10474-016-0606-1
[15]	Z. Kewen, H. J. Lai, J. Zhou, Hamiltonian-connected graphs, Comput. Math. Appl., 55 (2008), 2707–2714.
[16]	R. Kužel, L. Xiong, Every 4–connected line graph is Hamiltonian if and only if it is Hamiltonian connected, In: R. Kuzel, Hamiltonian properties of graphs, Ph.D Thesis, U. W. B. Pilsen, 2004.
[17]	I. Lukovits, Indicators for atoms included in cycles, J. Chem. Inf. Comput. Sci., 36 (1996), 65–68. doi: 10.1021/ci950082o
[18]	I. Lukovits, The detour index, Croat. Chem. Acta, 69 (1996), 873–882.
[19]	I. Lukovits, M. Razinger, On calculation of the detour index, J. Chem. Inf. Comput. Sci., 37 (1997), 283–286. doi: 10.1021/ci960034j
[20]	O. Ore, Hamilton-connected graphs, J. Math. Pure Appl., 42 (1963), 21–27.
[21]	S. Qiang, Z. Qain, A. Yahui, The Hamiltonicity of generalized honeycomb torus networks, Inf. Process. Lett., 115 (2005), 104–111.
[22]	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. doi: 10.1021/ci980024d
[23]	H. Raza, S. Hayat, X. F. Pan, Binary locating-dominating sets in rotationally-symmetric convex polytopes, Symmetry, 10 (2018), 727–745. doi: 10.3390/sym10120727
[24]	H. Raza, S. Hayat, X. F. Pan, On the fault-tolerant metric dimension of convex polytopes, Appl. Math. Comput., 393 (2018), 172–185.
[25]	H. Raza, J. B. Liu, S. Qu, On mixed metric dimension of rotationally-symmetric graphs, IEEE Access, 8 (2020), 11560–11569. doi: 10.1109/ACCESS.2019.2961191
[26]	A. Shabbir, M. F. Nadeem, T. Zamfirescu, The property of Hamiltonian connectedness in Toeplitz graphs, Complexity, 2020 (2020), 5608720.
[27]	A. Simić, M. Bogdanović, J. Milošević, The binary locating-dominating number of some convex polytopes, ARS Math. Cont., 13 (2017), 367–377. doi: 10.26493/1855-3974.973.479
[28]	I. A. Stewart, Sufficient conditions for Hamiltonicity in multiswapped networks, J. Parallel Distrib. Comput., 101 (2017), 17–26. doi: 10.1016/j.jpdc.2016.10.015
[29]	C. Thomassen, Hamiltonian-connected tournaments, J. Comb. Theory B, 28 (1980), 142–163. doi: 10.1016/0095-8956(80)90061-1
[30]	N. Trinajstić, S. Nikolić, Z. Mihalić, On computing the molecular detour matrix, Int. J. Quantum Chem., 65 (1998), 415–419.
[31]	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. doi: 10.1021/ci960149n
[32]	B. Wei, Hamiltonian paths and Hamiltonian connectivity in graphs, Discrete Math., 121 (1993), 223–228. doi: 10.1016/0012-365X(93)90555-8
[33]	J. Wei, Z. You, H. J. Lai, Spectral analogues of Erdös' theorem on Hamilton-connected graphs, Appl. Math. Comput., 340 (2019), 242–250.
[34]	X. Yang, J. Du, L. Xiong, Forbidden subgraphs for super-Eulerian and Hamiltonian graphs, Discrete Appl. Math., 288 (2021), 192–200. doi: 10.1016/j.dam.2020.08.034
[35]	X. Yang, D. J. Evans, H. J. Lai, G. M. Megson, Generalized honeycomb torus is Hamiltonian, Inf. Process. Lett., 92 (2004), 31–37. doi: 10.1016/j.ipl.2004.05.017
[36]	H. Whitney, Congruent graphs and the connectivity of graphs, Am. J. Math., 54 (1932), 150–168. doi: 10.2307/2371086
[37]	Q. Zhou, L. Wang, Some sufficient spectral conditions on Hamilton-connected and traceable graphs, Linear Multilinear A., 65 (2017), 224–234. doi: 10.1080/03081087.2016.1182463
[38]	Q. Zhou, L. Wang, Y. Lu, Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree, Linear Algebra Appl., 592 (2020), 48–64. doi: 10.1016/j.laa.2020.01.021
[39]	Q. Zhou, L. Wang, Y. Lu, Wiener index and Harary index on Hamilton-connected graphs with large minimum degree, Discrete Appl. Math., 247 (2018), 180–185. doi: 10.1016/j.dam.2018.03.063

Reader Comments

Your name:*

Email:*
© 2021 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)