2023/03/17 by Leyou Xu, Xu, Leyou, Chengli Li +3
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2303.09741
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átal's toughness conjecture, stating that there exists a constant t0 such that every t0-tough graph with at least three vertices is Hamiltonian, is still open in general. Chvátal and Erdös \citeCE proved that, for any integer k≥ 1, every max\2,k\-connected (k+1)P1-free graph on at least three vertices is Hamiltonian. Along the Chvátal-Erdös theorem, Shi and Shan \citeSS proved that, for any integer k≥ 4, every 4-tough 2k-connected (P2∪ kP1)-free graph with at least three vertices is Hamiltonian, and furthermore, they proposed a conjecture that for any integer k≥ 1, any 1-tough 2k-connected (P2∪ kP1)-free graph is Hamiltonian. In this paper, we confirm the conjecture, and furthermore, we show that if k≥ 3, then the condition `2k-connected' may be weakened to be `2(k-1)-connected'. As an immediate consequence, for any integer k≥ 3, every (k-1)-tough (P2∪ kP1)-free graph is Hamiltonian. This improves the result of Hatfield and Grimm \citeHG, stating that every 3-tough (P2∪ 3P1)-free graph is Hamiltonian.