Cyclability of $id$-cycles in graphs

Abstract

Let $G$ be a graph on $n$ vertices and $C^{\prime }=v_0{v}_1\cdots v_{p-1}{v}_0$ a vertex sequence of $G$ with $p\ge 3$ ($v_i\ne v_j$ for all $i,j=0,1,\dots ,p-1$, $i\ne j$). If for any successive vertices $v_i$, $v_{i+1}$ on $C^{\prime }$, either $v_i{v}_{i+1}\in E(G)$ or both of the first implicit-degrees of $v_i$ and $v_{i+1}$ are at least $n/2$ (indices are taken modulo $p$), then $C^{\prime }$ is called an $id$-cycle of $G$. In this paper, we prove that for every $id$-cycle $C^{\prime }$, there exists a cycle $C$ in $G$ with $V(C^{\prime })\subseteq V(C)$. This generalizes several early results on the Hamiltonicity and cyclability of graphs.

9 pages. Actually, this paper was finished in 2014 and has been submitted for publication in Feb. 2015