English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a graph $H$, a graph $G$ is $H$-free if $G$ does not contain $H$ as aninduced subgraph. For a positive real number $t$, a non-complete graph $G$ issaid to be $t$-tough if for every vertex cut $S$ of $G$, the ratio of $|S|$ tothe number of components of $G-S$ is at least $t$. A complete graph is said tobe $t$-tough for any $t>0$. Chv\'{a}tal's toughness conjecture, stating thatthere exists a constant $t_0$ such that every $t_0$-tough graph with at leastthree vertices is Hamiltonian, is still open in general. Chv\'{a}tal andErd\"{o}s \cite{CE} proved that, for any integer $k\ge 1$, every$\max\{2,k\}$-connected $(k+1)P_1$-free graph on at least three vertices isHamiltonian. Along the Chv\'{a}tal-Erd\"{o}s theorem, Shi and Shan \cite{SS}proved that, for any integer $k\ge 4$, every $4$-tough $2k$-connected $(P_2\cupkP_1)$-free graph with at least three vertices is Hamiltonian, and furthermore,they proposed a conjecture that for any integer $k\ge 1$, any $1$-tough$2k$-connected $(P_2\cup kP_1)$-free graph is Hamiltonian. In this paper, weconfirm the conjecture, and furthermore, we show that if $k\ge 3$, then thecondition `$2k$-connected' may be weakened to be `$2(k-1)$-connected'. As animmediate consequence, for any integer $k\ge 3$, every $(k-1)$-tough $(P_2\cupkP_1)$-free graph is Hamiltonian. This improves the result of Hatfield andGrimm \cite{HG}, stating that every $3$-tough $(P_2\cup 3P_1)$-free graph isHamiltonian.

Hamiltonicity of $1$-tough $(P_2\cup kP_1)$-free graphs