Hamiltonicity of 1-tough (P₂ KP₁)-free graphs

DOI10.1016/J.DISC.2023.113755arXiv2303.09741OpenAlexW4387806281MaRDI QIDQ6184533FDOQ6184533

Authors:

Publication date: 25 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a graph $H$, a graph $G$ is $H$-free if $G$ does not contain $H$ as an induced subgraph. For a positive real number $t$, a non-complete graph $G$ is said to be $t$-tough if for every vertex cut $S$ of $G$, the ratio of $|S|$ to the number of components of $G-S$ is at least $t$. A complete graph is said to be $t$-tough for any $t>0$. Chv'{a}tal's toughness conjecture, stating that there exists a constant $t_0$ such that every $t_0$-tough graph with at least three vertices is Hamiltonian, is still open in general. Chv'{a}tal and Erd"{o}s cite{CE} proved that, for any integer $kge1$, every $max2,k$-connected $(k+1)P_1$-free graph on at least three vertices is Hamiltonian. Along the Chv'{a}tal-Erd"{o}s theorem, Shi and Shan cite{SS} proved that, for any integer $kge4$, every $4$-tough $2k$-connected $(P_{2}cupk{P}_1)$-free graph with at least three vertices is Hamiltonian, and furthermore, they proposed a conjecture that for any integer $kge1$, any $1$-tough $2k$-connected $(P_{2}cupk{P}_1)$-free graph is Hamiltonian. In this paper, we confirm the conjecture, and furthermore, we show that if $kge3$, then the condition `$2k$-connected' may be weakened to be `$2(k-1)$-connected'. As an immediate consequence, for any integer $kge3$, every $(k-1)$-tough $(P_{2}cupk{P}_1)$-free graph is Hamiltonian. This improves the result of Hatfield and Grimm cite{HG}, stating that every $3$-tough $(P_{2}cup3P_1)$-free graph is Hamiltonian.

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

Recommendations

• A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs
• Some conditions for Hamiltonian cycles in 1-tough \((K_2 \cup kK_1)\)-free graphs
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs

zbMATH Keywords

toughnessHamiltonian graph\(( P_2 \cup k P_1)\)-free graph

Mathematics Subject Classification ID

Combinatorics (05-XX) Number theory (11-XX)

Cites Work

• A note on Hamiltonian circuits
• Title not available (Why is that?)
• Not every 2-tough graph is Hamiltonian
• Toughness in graphs -- a survey
• Tough graphs and Hamiltonian circuits.
• More than one tough chordal planar graphs are Hamiltonian
• Forbidden subgraphs for Hamiltonicity of 1-tough graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• 10-tough chordal graphs are Hamiltonian
• An Ore-type condition for Hamiltonicity in tough graphs
• 1-tough cocomparability graphs are hamiltonian
• Toughness and Hamiltonicity in \(k\)-trees
• Hamiltonian cycles in 1-tough graphs
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-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
• Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs

This page was built for publication: Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs

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