Hamiltonian cycles in 7-tough (P₃ 2P₁)-free graphs

DOI10.1016/J.DISC.2022.113069MaRDI QIDQ2675828zbMATH OpenOpenAlexWikidataFDO

Authors Songling Shan, Yuping Gao

Publication date 26 September 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Chvatal toughness conjectureHamiltonian graphstoughness of a graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The toughness of a noncomplete graph $G$ is the maximum real number $t$ such that the ratio of $|S|$ to the number of components of $G-S$ is at least $t$ for every cutset $S$ of $G$, and the toughness of a complete graph is defined to be $infty$. Determining the toughness for a given graph is NP-hard. Chv'{a}tal's toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_{3}cup2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_{3}cup2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chv'{a}tal's toughness conjecture for $(P_{3}cup2P_1)$-free graphs by showing that every 7-tough $(P_{3}cup2P_1)$-free graph on at least three vertices is hamiltonian.

Review text

A \(t\)-tough graph is a noncomplete graph \(G\) such that \(|S| \geq t \cdot c(G-S)\) for every cutset \(S\) of \(G\). This concept is strongly related to the Hamiltonicity of graphs. In the paper under review, the authors prove that every \(7\)-tough \((P_3 \cup 2P_1)\)-free graph with at least three vertices is Hamiltonian.

Recommendations

• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• Hamiltonian cycles in 3-tough \(2K_2\)-free graphs
• Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs
• Hamilton cycles in 1-tough triangle-free graphs
• A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs
• A sufficient condition for Hamiltonian cycles in tough graphs
• Hamiltonian cycles in 1-tough graphs
• On hamiltonicity of 1-tough triangle-free graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• scientific article; zbMATH DE number 4177107

Cites work

• 1-tough cocomparability graphs are hamiltonian
• 10-tough chordal graphs are Hamiltonian
• A Theorem on Planar Graphs
• An Ore-type condition for Hamiltonicity in tough graphs
• Factors and factorizations of graphs. Proof techniques in factor theory
• Finding Hamiltonian circuits in interval graphs
• Forbidden subgraphs for Hamiltonicity of 1-tough graphs
• Hamiltonian cycles in 3-tough \(2K_2\)-free graphs
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• scientific article; zbMATH DE number 4043881 (Why is no real title available?)
• scientific article; zbMATH DE number 1124477 (Why is no real title available?)
• Long cycles in graphs with prescribed toughness and minimum degree
• More than one tough chordal planar graphs are Hamiltonian
• Not every 2-tough graph is Hamiltonian
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Tough graphs and Hamiltonian circuits.
• Tough spiders
• Toughness and Hamiltonicity in k-trees
• Toughness, hamiltonicity and split graphs

Cited in

(16)

• On some intriguing problems in Hamiltonian graph theory---a survey
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs
• Hamiltonian cycles in 3-tough \(2K_2\)-free graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs
• Some conditions for Hamiltonian cycles in 1-tough (K₂ kK₁)-free graphs
• Hamiltonicity of 1-tough (P₂ KP₁)-free graphs
• An Ore-type condition for hamiltonicity in tough graphs and the extremal examples
• Toughness properties of arbitrarily partitionable graphs
• On minimally 1-tough (P₂ 3P₁)-free graphs
• Some conditions for pancyclicity in t-tough graphs
• Every 2k-connected (P₂ kP₁)-free graph with toughness greater than one is Hamiltonian-connected
• Hamilton cycles in tough (2P₂ P₁)-free graphs
• Hamiltonian cycles in tough (P₄ P₁)-free graphs
• Toughness and prism-Hamiltonicity of \(P_4\)-free graphs

This page was built for publication: Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs

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