A Fan-type condition for cycles in 1-tough and k-connected (P2 ∪ kP1)-free graphs

Zhiquan Hu, Jie Wang and Changlong Shen

Applied Mathematics and Computation, 2025, vol. 494, issue C

Abstract: For a graph G, define μk(G):=min⁡{maxx∈S⁡dG(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 called 1-tough if for each cut set S⊆V(G), G−S has no more than |S| components. Recently, Shi and Shan [19] 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. [20] and Ota and Sanka [16], respectively. In this article, we generalize the above results through the following Fan-type theorem: If G is a 1-tough and k-connected (P2∪kP1)-free graph and satisfies μk+1(G)≥7k−65, where k≥2 is an integer, then G is hamiltonian or the Petersen graph.

Keywords: 1-tough; (P2 ∪ kP1)-free; Fan-type condition; Hamiltonian cycle (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630032500027X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:494:y:2025:i:c:s009630032500027x

DOI: 10.1016/j.amc.2025.129300

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().