Geodesic
On $s$-hamiltonian-connected line graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 297-315 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

For an integer s≥ 0, G is s-hamiltonian-connected if for any vertex subset S⊆ V(G) with |S|≤ s, G-S 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: line graph, claw-free graph, $s$-hamiltonian-connected, collapsible graphs, reductions 
@article{DMGT_2024_44_1_a14,
     author = {Ma, Xiaoling and Lai, Hong-Jian and Zhan, Mingquan and Zhang, Taoye and Zhou, Ju},
     title = {On $s$-hamiltonian-connected line graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {297--315},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a14/}
}
TY  - JOUR
AU  - Ma, Xiaoling
AU  - Lai, Hong-Jian
AU  - Zhan, Mingquan
AU  - Zhang, Taoye
AU  - Zhou, Ju
TI  - On $s$-hamiltonian-connected line graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 297
EP  - 315
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a14/
LA  - en
ID  - DMGT_2024_44_1_a14
ER  - 
%0 Journal Article
%A Ma, Xiaoling
%A Lai, Hong-Jian
%A Zhan, Mingquan
%A Zhang, Taoye
%A Zhou, Ju
%T On $s$-hamiltonian-connected line graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 297-315
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a14/
%G en
%F DMGT_2024_44_1_a14
Ma, Xiaoling; Lai, Hong-Jian; Zhan, Mingquan; Zhang, Taoye; Zhou, Ju. On $s$-hamiltonian-connected line graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 297-315. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a14/

[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-2

[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.3190120105

[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-Q

[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.056

[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-y

[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-3

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

[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.009

[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.015

[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.2040

[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).

[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.120

[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.21713

[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.005

[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.006

[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.3190080116

[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.20498

[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.21743

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

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

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