2024/07/27 by Hu, Zhiquan, Wang, Jie, Shen, Changlong
#05C38 #05C45 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2407.19149
For a graph G, let μk(G):=min~\maxx∈ SdG(x):~S∈ Sk\, where Sk is the set consisting of all independent sets \u1,…,uk\ of G such that some vertex, say ui (1≤ i≤ k), is at distance two from every other vertex in it. A graph G is 1-tough if for each cut set S⊆ V(G), G-S has at most |S| components. Recently, Shi and Shan \citeShi conjectured that for each integer k≥ 4, being 2k-connected is sufficient for 1-tough (P2∪ kP1)-free graphs to be hamiltonian, which was confirmed by Xu et al. \citeXu and Ota and Sanka \citeOta2, respectively. In this article, we generalize the above results through the following Fan-type theorem: Let k be an integer with k≥ 2 and let G be a 1-tough and k-connected (P2∪ kP1)-free graph with μk+1(G)≥(7k-6)/(5), then G is hamiltonian or the Petersen graph.