×

Hamilton-connectivity of line graphs with application to their detour index. (English) Zbl 1486.05175


MSC:

05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdullah, HO; Omar, ZI, Edge restricted detour index of some graphs, J. Discrete Math. Sci. Crypt., 23, 4, 861-877 (2020) · Zbl 1482.05075
[2] Alspach, B., The classification of Hamiltonian generalized petersen graphs, J. Combin. Theor. Ser. B, 34, 293-312 (1983) · Zbl 0516.05034
[3] Alspach, B.; Liu, J., On the Hamilton-connectivity of generalized Petersen graphs, Discrete Math., 309, 5461-5473 (2009) · Zbl 1189.05083
[4] Chang, J-M; Yang, J-S; Wang, Y-L; Chang, Y., Panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs, Networks, 44, 4, 302-310 (2004) · Zbl 1055.05076
[5] Chartrand, G.: Graphs and their associated line graphs. Ph.D. dissertation, Michigan State University (1964)
[6] Chartrand, G.; Hobbs, AM; Jung, HA; Kapoor, SF; Nash-Williams, CSJ, The square of a block is Hamiltonian connected, J. Combin. Theor. Ser. B, 16, 3, 290-292 (1974) · Zbl 0277.05129
[7] Dobrynin, AA; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211-249 (2001) · Zbl 0982.05044
[8] Du, C., Minimum detour index of bicyclic graphs, MATCH Commun. Math. Comput. Chem., 68, 1, 357-370 (2012) · Zbl 1289.05229
[9] Fang, W., Cai, Z.Q., Li, X.X.: Minimum detour index of tricyclic graphs. J. Chem. 2019, ID 6031568 (2019)
[10] Frucht, R., A canonical representation of trivalent Hamiltonian graphs, J. Graph Theory, 1, 45-60 (1976) · Zbl 0358.05029
[11] Garey, MR; Johnson, DS, Computers and Intractability: A Guide to the Theory of NP-Completeness, 199 (1983), New York: W. H. Freeman, New York
[12] Gordon, VS; Orlovich, YL; Werner, F., Hamiltonian properties of triangular grid graphs, Discrete Math., 308, 6166-6188 (2008) · Zbl 1158.05040
[13] Harary, F., Graph Theory (1969), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0182.57702
[14] Hung, RW; Keshavarz-Kohjerdi, F.; Lin, CB; Chen, JS, The Hamiltonian connectivity of alphabet supergrid graphs, Int. J. Appl. Math., 49, 1, 1-10 (2019) · Zbl 1512.05247
[15] Kaladevi, V.; Abinayaa, A., On detour distance Laplacian energy, J. Inf. Math. Sci., 9, 3, 721-732 (2017)
[16] Karbasioun, A.; Ashrafi, AR; Diudea, MV, Distance and detour matrices of an infinite class of dendrimer nanostars, MATCH Commun. Math. Comput. Chem., 63, 1, 239-246 (2010) · Zbl 1299.05095
[17] Kewen, Z.; Lai, HJ; Zhou, J., Hamiltonian-connected graphs, Comput. Math. Appl., 55, 12, 2707-2714 (2008) · Zbl 1142.05332
[18] Kriesell, M., All 4-connected line graphs of claw free graphs are Hamiltonian connected, J. Combin. Theor. Ser. B, 82, 2, 306-315 (2001) · Zbl 1027.05059
[19] Kužel, R., Xiong, L.: Every 4-connected line graph is Hamiltonian if and only if it is Hamiltonian connected. In: Kuzel, R. (ed) Hamiltonian properties of graphs. Ph.D Thesis, U.W.B. Pilsen (2004)
[20] Lai, HJ; Shao, Y.; Yu, G.; Zhan, M., Hamiltonian connectedness in 3-connected line graphs, Discrete Appl. Math., 157, 5, 982-990 (2009) · Zbl 1169.05344
[21] Liu, J.; Yu, A.; Wang, K.; Lai, HJ, Degree sum and Hamiltonian-connected line graphs, Discrete Math., 341, 5, 1363-1379 (2018) · Zbl 1383.05274
[22] Lukovits, I., Indicators for atoms included in cycles, J. Chem. Inf. Comput. Sci., 36, 65-68 (1996)
[23] Lukovits, I., The detour index, Croat. Chem. Acta, 69, 873-882 (1996)
[24] Lukovits, I.; Razinger, M., On calculation of the detour index, J. Chem. Inf. Comput. Sci., 37, 283-286 (1997)
[25] Mahmiani, A.; Khormali, O.; Iranmanesh, A., The edge versions of detour index, MATCH Commun. Math. Comput. Chem., 62, 2, 419-431 (2009) · Zbl 1199.05093
[26] Matthews, MM; Sumner, DP, Hamiltonian results in \(K_{1,3}\)-free graphs, J. Graph Theory, 8, 139-146 (1984) · Zbl 0536.05047
[27] Ore, O., Hamilton-connected graphs, J. Math. Pure Appl., 42, 21-27 (1963) · Zbl 0106.37103
[28] Qi, X.; Zhou, B., Detour index of a class of unicyclic graphs, Filomat, 24, 1, 29-40 (2010) · Zbl 1265.05201
[29] Qiang, S.; Qain, Z.; Yahui, A., The Hamiltonicity of generalized honeycomb torus networks, Inf. Process. Lett., 115, 2, 104-111 (2005) · Zbl 1302.68214
[30] Rücker, G.; Rücker, C., Symmetry-aided computation of the detour matrix and the detour index, J. Chem. Inf. Comput. Sci., 38, 710-714 (1998) · JFM 30.0083.03
[31] Ryjáček, Z., On a closure concept in claw-free graphs, J. Combin. Theor. Ser. B, 70, 217-224 (1997) · Zbl 0872.05032
[32] Schwenk, A., Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, J. Combin. Theor. Ser. B, 47, 53-59 (1989) · Zbl 0626.05038
[33] Shabbir, A., Nadeem, M.F., Zamfirescu, T.: The property of Hamiltonian connectedness in Toeplitz graphs. Complexity 2020, ID 5608720 (2020) · Zbl 1435.05125
[34] Stewart, IA, Sufficient conditions for Hamiltonicity in multiswapped networks, J. Parallel Distrib. Comput., 101, 17-26 (2017)
[35] Thomassen, C., Cycles in Graphs, 463 (1985), Amsterdam: North-Holland, Amsterdam · Zbl 0606.05039
[36] Thomassen, C., Hamiltonian-connected tournaments, J. Combin. Theor. Ser. B, 28, 2, 142-163 (1980) · Zbl 0435.05026
[37] Trinajstić, N.; Nikolić, S.; Mihalić, Z., On computing the molecular detour matrix, Int. J. Quantum Chem., 65, 415-419 (1998)
[38] Trinajstić, N.; Nikolić, S.; Lučić, B.; Amić, D.; Mihalić, Z., The detour matrix in chemistry, J. Chem. Inf. Comput. Sci., 37, 631-638 (1997)
[39] Watkins, ME, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory, 6, 152-164 (1969) · Zbl 0175.50303
[40] Wei, B., Hamiltonian paths and Hamiltonian connectivity in graphs, Discrete Math., 121, 223-228 (1993) · Zbl 0796.05063
[41] Wei, J.; You, Z.; Lai, HJ, Spectral analogues of Erdös’ theorem on Hamilton-connected graphs, Appl. Math. Comput., 340, 242-250 (2019) · Zbl 1428.05206
[42] Whitney, H., Congruent graphs and the connectivity of graphs, Am. J. Math., 54, 150-168 (1932) · Zbl 0003.32804
[43] Williamson J.E.: On Hamiltonian-connected graphs. Ph.D Thesis, Western Michigan University (1973)
[44] Wu, R.; Deng, H., On the detour index of a chain of C20 fullerenes, J. Optoelectron. Biomed. Mater., 8, 2, 45-48 (2016)
[45] Yang, X.; Du, J.; Xiong, L., Forbidden subgraphs for super-Eulerian and Hamiltonian graphs, Discrete Appl. Math., 288, 192-200 (2021) · Zbl 1451.05133
[46] Yang, X.; Evans, DJ; Lai, HJ; Megson, GM, Generalized honeycomb torus is Hamiltonian, Inf. Process. Lett., 92, 31-37 (2004) · Zbl 1173.68426
[47] Zhan, S., Hamiltonian connectedness of line graphs, ARS Combin., 22, 89-95 (1986) · Zbl 0611.05038
[48] Zhan, S., On Hamiltonian line graphs and connectivity, Discrete Math., 89, 89-95 (1991) · Zbl 0727.05037
[49] Zhou, B.; Cai, X., On detour index, MATCH Commun. Math. Comput. Chem., 63, 199-210 (2010) · Zbl 1225.05090
[50] Zhou, Q.; Wang, L., Some sufficient spectral conditions on Hamilton-connected and traceable graphs, Linear Multilinear Algebra, 65, 2, 224-234 (2017) · Zbl 1356.05085
[51] Zhou, Q.; Wang, L.; Lu, Y., Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree, Linear Algebra Appl., 592, 48-64 (2020) · Zbl 1437.05161
[52] Zhou, Q.; Wang, L.; Lu, Y., Wiener index and Harary index on Hamilton-connected graphs with large minimum degree, Discrete Appl. Math., 247, 180-185 (2018) · Zbl 1394.05064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.