A Fan-type condition for cycles in $1$-tough and $k$-connected $(P_2\cup k{P}_1)$-free graphs

Abstract

For a graph $G$, let ${\mu }_k(G):=\min \{{\max }_{x\in S}{d}_G(x):S\in {\mathcal{S}}_k\}$, where ${\mathcal{S}}_k$ is the set consisting of all independent sets $\{u_1,\dots ,u_k\}$ of $G$ such that some vertex, say $u_i$ ($1\le i\le k$), is at distance two from every other vertex in it. A graph $G$ is $1$-tough if for each cut set $S\subseteq V(G)$, $G-S$ has at most $|S|$ components. Recently, Shi and Shan \cite{Shi} conjectured that for each integer $k\ge 4$, being $2k$-connected is sufficient for $1$-tough $(P_2\cup k{P}_1)$-free graphs to be hamiltonian, which was confirmed by Xu et al. \cite{Xu} and Ota and Sanka \cite{Ota2}, respectively. In this article, we generalize the above results through the following Fan-type theorem: Let $k$ be an integer with $k\ge 2$ and let $G$ be a $1$-tough and $k$-connected $(P_2\cup k{P}_1)$-free graph with ${\mu }_{k+1}(G)\ge \frac{7k-6}{5}$, then $G$ is hamiltonian or the Petersen graph.

19 pages, 4 figures