The Hamiltonicity of essentially 9‐connected line graphs

DOI10.1002/JGT.22653MaRDI QIDQ6055939zbMATH OpenOpenAlexFDO

Authors Tomáš Kaiser, Petr Vrána

Publication date 29 September 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.00042

zbMATH Keywords

essential edge-connectivityHamilton cycleHamilton-connectivityline graph

Mathematics Subject Classification ID

Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Yang et al. proved that every 3-connected, essentially 11-connected line graph is Hamilton-connected. This was extended by Li and Yang to 3-connected, essentially 10-connected graphs. Strengthening their result further, we prove that 3-connected, essentially 9-connected line graphs are Hamilton-connected. We use a method based on quasigraphs in combination with the discharging technique. The result extends to claw-free graphs.

Recommendations

• scientific article; zbMATH DE number 3987316
• On hamiltonian line graphs and connectivity
• scientific article; zbMATH DE number 1094037
• Hamiltonicity of 3-connected line graphs
• On \(s\)-Hamiltonian-connected line graphs
• scientific article; zbMATH DE number 3946175
• On hamiltonian line graphs of hypergraphs
• Hamiltonian connectedness in 3-connected line graphs
• On hamiltonian line graphs
• scientific article; zbMATH DE number 68360

Cites work

• Collapsible graphs and Hamiltonian connectedness of line graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• Eulerian subgraphs and Hamilton-connected line graphs
• Every 3-connected essentially 10-connected line graph is Hamilton-connected
• Every 3-connected, essentially 11-connected line graph is Hamiltonian
• Graph theory
• Hamilton cycles in 5-connected line graphs
• Hamiltonicity of 3-connected line graphs
• Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs
• On \(s\)-Hamiltonian-connected line graphs
• On the Problem of Decomposing a Graph into n Connected Factors
• Quasigraphs and skeletal partitions
• Reflections on graph theory

Cited in

(7)

• Every 3-connected essentially 10-connected line graph is Hamilton-connected
• Quasigraphs and skeletal partitions
• Spanning tree packing and 2-essential edge-connectivity
• Every 3-connected, essentially 11-connected line graph is Hamiltonian
• Every 3-connected, essentially 11-connected line graph is Hamiltonian
• On k-edge-Hamilton-connected line graphs
• Fault Hamiltonicity and fault Hamiltonian connectivity of (n, k)-bubble sort graphs

This page was built for publication: The Hamiltonicity of essentially 9‐connected line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6055939)