Article in volume
Authors:
Title:
On $s$-hamiltonian-connected line graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 297-315
Received: 2021-09-27 , Revised: 2021-12-27 , Accepted: 2021-12-27 , Available online: 2022-02-08 , https://doi.org/10.7151/dmgt.2448
Abstract:
For an integer $s\ge 0$, $G$ is $s$-hamiltonian-connected if for any vertex
subset $S\subseteq V(G)$ with $|S|\le 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\ge 3$, every $(s+4)$-connected line graph is $s$-hamiltonian-connected.
(ii) For $s\ge 0$, every $(s+4)$-connected line graph of a claw-free graph is $s$-hamiltonian-connected.
(i) For $s\ge 3$, every $(s+4)$-connected line graph is $s$-hamiltonian-connected.
(ii) For $s\ge 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
References:
- 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 - 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 - 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 - 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 - 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 - 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 - F. Jaeger, A note on sub-Eulerian graphs, J. Graph Theory 3 (1979) 91–93.
https://doi.org/10.1002/jgt.3190030110 - 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 - 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 - 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 - 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).
- 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 - 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 - 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 - 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 - M.M. Matthews and D.P. Sumner, Hamiltonian results in $K_{1,3}$-free graphs, J. Graph Theory 8 (1984) 139–146.
https://doi.org/10.1002/jgt.3190080116 - 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 - 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 - Y. Shao, Claw-Free Graphs and Line Graphs, Ph.D. Dissertation (West Virginia University, 2005).
- C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309–324.
https://doi.org/10.1002/jgt.3190100308 - S. Zhan, Hamiltonian connectedness of line graphs, Ars Combin. 22 (1986) 89–95.
Close