A new sufficient condition for pancyclability of graphs

International audienceLet $G$ be a graph of order $n$ and $S$ be a set of $s$ vertices. We call $G$, $S$-pancyclable, if for every $i$ with $3\leq i \leq s$, there exists a cycle $C$ in $G$ such that $|V(C)\cap S|=i$. For any two nonadjacent vertices $u,v$ of $S$, we say that $u,v$ are of distance 2 in $S$, denoted by $d_S(u,v)=2$, if there is a path $P$ in $G$ connecting $u$ and $v$ such that $|V(P)\cap S|\leq 3$. In this paper, we will prove that: Let $G$ be a 2-connected graph of order $n$ and $S$ be a subset of $V(G)$ with $|S|\geq 3$. If $\max \{d(u),d(v)\} \geq n/2$ for all pairs of vertices $u,v$ of $S$ with $d_S(u,v)=2$, then $G$ is $S$-pancyclable or else $|S|=4r$ and $G[S]$ is a spanning subgraph of $F_{4r}$, or else $|S|=n$ is even and $G$ is the complete bipartite graph $K_{n/2,n/2}$, or else $|S|=n≥6$ is even and $G$ is $K'_{n/2,n/2}$, or else $G[S] = K_{2,2}$ and the structure of $G$ is well characterized. This generalizes a result of Benhocine and Wojda for the case when $S = V (G)$. [A. Benhocine, A.P. Wojda, The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graph, J. Combin. Theory B 42 (1987) 167–180]