Every 4-connected \{claw, hourglass\}-free graph is 2-Hamiltonian
For an integer \(s\ge0\), a graph \(G(V,E)\) is \(s\)-Hamiltonian if, for any \(s\)-subset \(X\subseteq V\), \(G-X\) is Hamiltonian; an alternative definition is discussed in \S2 of the paper. \(\Gamma\), the hourglass, is the unique 5-vertex graph with degree sequence \(4,2,2,2,2\) -- this is the graph the authors called \(\Gamma_0\) in their paper (jointly with other authors) [\textit{A. Kabela} et al., Discrete Math. 348, No. 2, Article ID 114305, 19 p. (2025; Zbl 1553.05100)]; the claw is \(K_{1,3}\). \(G\) is \(\{K_{1,3},\Gamma\}\)-free if it contains neither of the two ``forbidden subgraphs as an induced subgraph. The main result of this paper is Theorem 1: Let \(s\ge2\) be an integer, and let \(G\) be an \((s+2)\)-connected \(\{K_{1,3},\Gamma\}\)-free graph. Then \(G\) is \(s\)-Hamiltonian. This theorem is proved by induction on \(s\), beginning with the titular theorem, Theorem 2, which is the case \(s=2\). A consequence of Theorem 1 is Corollary 3: (i) Let \(s\ge2\) be an integer, and let \(G\) be a \(\left\{K_{1,3},\Gamma\right\}\)-free graph. Then \(G\) is \(s\)-Hamiltonian if and only if \(G\) is \((s+2)\)-connected. (ii) For an integer \(s\ge2\), \(s\)-Hamiltonicity is polynomial-time decidable in the class of \(\{K_{1,3},\Gamma\}\)-free graphs.
- A reduction method to find spanning Eulerian subgraphs
- Contractibility techniques as a closure concept
- Edge-connectivity and edge-disjoint spanning trees
- Forbidden subgraphs, hamiltonicity and closure in claw-free graphs
- Forbidden subgraphs, stability and hamiltonicity
- Graph theory
- Graphs without spanning closed trails
- Hamiltonian properties of 3-connected \{claw,hourglass\}-free graphs
- Hamiltonian results inK1,3-free graphs
- scientific article; zbMATH DE number 3102314 (Why is no real title available?)
- Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs
- On 1-Hamilton-connected claw-free graphs
- On a closure concept in claw-free graphs
- On Eulerian and Hamiltonian Graphs and Line Graphs
- On the s-hamiltonianicity of an hourglass-free line graph
- Reflections on graph theory
- Stability of hereditary graph classes under closure operations
This page was built for publication: Every 4-connected \{claw, hourglass\}-free graph is 2-Hamiltonian
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7231827)
