1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On s-Hamiltonian-Connected Line Graphs

Published Online: 18 Feb 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 27 Sep 2021
Accepted: 27 Dec 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

For an integer s ≥ 0, G is s-hamiltonian-connected if for any vertex subset SV (G) with |S| ≤ s, GS is hamiltonian-connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see [Reflections on graph theory, J. Graph Theory 10 (1986) 309–324]), and Kužel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian-connected (see [Z. Ryjáček and P. Vrána, Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs, J. Graph Theory 66 (2011) 152–173]). In this paper we prove the following. (i) For s ≥ 3, every (s + 4)-connected line graph is s-hamiltonian-connected. (ii) For s ≥ 0, every (s + 4)-connected line graph of a claw-free graph is s-hamiltonian-connected.

Keywords

MSC 2010

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Elsevier Science Publishing Co. Inc. New York NY, 1976). https://doi.org/10.1007/978-1-349-03521-210.1007/978-1-349-03521-2 Search in Google Scholar

[2] P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44. https://doi.org/10.1002/jgt.319012010510.1002/jgt.3190120105 Search in Google Scholar

[3] P.A. Catlin, Z. Han and H.-J. Lai, Graphs without spanning closed trails, Discrete Math. 160 (1996) 81–91. https://doi.org/10.1016/S0012-365X(95)00149-Q10.1016/S0012-365X(95)00149-Q Search in Google Scholar

[4] P.A. Catlin, H.-J. Lai and Y. Shao, Edge-connectivity and edge-disjoint spanning trees, Discrete Math. 309 (2009) 1033–1040. https://doi.org/10.1016/j.disc.2007.11.05610.1016/j.disc.2007.11.056 Search in Google Scholar

[5] Z.-H. Chen, H.-J. Lai, W. Shiu and D.Y. Li, An s-hamiltonian line graph problem, Graphs Combin. 23 (2007) 241–248. https://doi.org/10.1007/s00373-007-0727-y10.1007/s00373-007-0727-y Search in Google Scholar

[6] F. Harary and C.St.J.A. Nash-Williams, On eulerian and hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965) 701–710. https://doi.org/10.4153/CMB-1965-051-310.4153/CMB-1965-051-3 Search in Google Scholar

[7] F. Jaeger, A note on sub-Eulerian graphs, J. Graph Theory 3 (1979) 91–93. https://doi.org/10.1002/jgt.319003011010.1002/jgt.3190030110 Search in Google Scholar

[8] T. Kaiser, Z. Ryjáček and P. Vrána, On 1-Hamilton-connected claw-free graphs, Discrete Math. 321 (2014) 1–11. https://doi.org/10.1016/j.disc.2013.12.00910.1016/j.disc.2013.12.009 Search in Google Scholar

[9] T. Kaiser and P. Vrána, Hamilton cycles in 5-connected line graphs, European J. Combin. 33 (2012) 924–947. https://doi.org/10.1016/j.ejc.2011.09.01510.1016/j.ejc.2011.09.015 Search in Google Scholar

[10] M. Kriesell, Every 4-connected line graph of claw-free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306–315. https://doi.org/10.1006/jctb.2001.204010.1006/jctb.2001.2040 Search in Google Scholar

[11] R. Kužel and L. Xiong, Every 4-connected line graph is hamiltonian if and only if it is hamiltonian-connected, in: R. Kučzel: Hamiltonian Properties of Graphs, Ph.D. Thesis, (U.W.B. Pilsen, 2004). Search in Google Scholar

[12] H.-J. Lai, Y. Liang and Y. Shao, On s-hamiltonian-connected line graphs, Discrete Math. 308 (2008) 4293–4297. https://doi.org/10.1016/j.disc.2007.07.12010.1016/j.disc.2007.07.120 Search in Google Scholar

[13] H.-J. Lai and Y. Shao, On s-hamiltonian line graphs, J. Graph Theory 74 (2013) 344–358. https://doi.org/10.1002/jgt.2171310.1002/jgt.21713 Search in Google Scholar

[14] H.-J. Lai, Y. Shao, G. Yu and M. Zhan, Hamiltonian connectedness in 3-connected line graphs, Discrete Appl. Math. 157 (2009) 982–990. https://doi.org/10.1016/j.dam.2008.02.00510.1016/j.dam.2008.02.005 Search in Google Scholar

[15] H.-J. Lai, M. Zhan, T. Zhang and J. Zhou, On s-hamiltonian line graphs of claw-free graphs, Discrete Math. 342 (2019) 3006–3016. https://doi.org/10.1016/j.disc.2019.06.00610.1016/j.disc.2019.06.006 Search in Google Scholar

[16] M.M. Matthews and D.P. Sumner, Hamiltonian results in K1,3-free graphs, J. Graph Theory 8 (1984) 139–146. https://doi.org/10.1002/jgt.319008011610.1002/jgt.3190080116 Search in Google Scholar

[17] Z. Ryjáček and P. Vrána, Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs, J. Graph Theory 66 (2011) 152–173. https://doi.org/10.1002/jgt.2049810.1002/jgt.20498 Search in Google Scholar

[18] Z. Ryjáček and P. Vrána, A closure for 1-Hamilton-connectedness in claw-free graphs, J. Graph Theory 75 (2014) 358–376. https://doi.org/10.1002/jgt.2174310.1002/jgt.21743 Search in Google Scholar

[19] Y. Shao, Claw-Free Graphs and Line Graphs, Ph.D. Dissertation (West Virginia University, 2005). Search in Google Scholar

[20] C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309–324. https://doi.org/10.1002/jgt.319010030810.1002/jgt.3190100308 Search in Google Scholar

[21] S. Zhan, Hamiltonian connectedness of line graphs, Ars Combin. 22 (1986) 89–95. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo