Hamiltonian cycles in 2‐tough 2K2 2{K}_{2}‐free graphs

DOI10.1002/JGT.22852zbMATH Open1522.05267arXiv2103.06760OpenAlexW4283169161WikidataQ114236126 ScholiaQ114236126MaRDI QIDQ6046653FDOQ6046653

Authors: Katsuhiro Ota 

Publication date: 5 October 2023

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

Abstract: A graph $G$ is called a $2K_2$-free graph if it does not contain $2K_2$ as an induced subgraph. In 2014, Broersma, Patel and Pyatkin showed that every 25-tough $2K_2$-free graph on at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3-tough is sufficient instead of 25-tough. In this paper, we show that every 2-tough $2K_2$-free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.

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

Recommendations

• Hamiltonian cycles in 3-tough \(2K_2\)-free graphs
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs
• Toughness, minimum degree, and the existence of 2‐factors
• Hamilton cycles in 1-tough triangle-free graphs
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• A sufficient condition for Hamiltonian cycles in tough graphs
• Hamiltonian cycles in 1-tough graphs
• Hamiltonian cycles in 2‐connected claw‐free‐graphs

zbMATH Keywords

Hamiltonian cycle2-factortoughness\(2K_2\)-free graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• Graph theory
• Toughness, hamiltonicity and split graphs
• Not every 2-tough graph is Hamiltonian
• Toughness in graphs -- a survey
• Tough graphs and Hamiltonian circuits.
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Toughness and the existence ofk-factors
• Chordality and 2-factors in tough graphs
• Edge-dominating cycles, \(k\)-walks and Hamilton prisms in \(2K_2\)-free graphs

Cited In (14)

• Title not available (Why is that?)
• Forbidden subgraphs and 2‐factors in 3/2‐tough graphs
• \(K_2\)-Hamiltonian graphs: I
• Some conditions for Hamiltonian cycles in 1-tough \((K_2 \cup kK_1)\)-free graphs
• Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs
• Hamiltonian cycles in 3-tough \(2K_2\)-free graphs
• Existence of 2-factors in tough graphs without forbidden subgraphs
• An Ore-type condition for hamiltonicity in tough graphs and the extremal examples
• A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Edge-dominating cycles, \(k\)-walks and Hamilton prisms in \(2K_2\)-free graphs

This page was built for publication: Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs

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