Variations of Pancyclic Graphs

Abstract

A graph $G$ of order $n$ is pancyclic if it contains a cycle of length $\ell$ for every $\ell$ such that $3\le \ell \le n$. If the graph is bipartite, then it contains no cycles of odd length. A balanced bipartite graph $G$ of order $2n$ is bipancyclic if it contains a cycle of length $\ell$ for every even $\ell$, such that $4\le \ell \le 2n$. A graph $G$ of order $n$ is called $k$-semipancyclic, $k\ge 0$, if there is no “gap” of $k+1$ among the cycle lengths in $G$, i.e., for no $\ell \le n-k$ is it the case that each of $C_{\ell },\dots ,C_{\ell +k}$ is missing from $G$. Generalizing this to bipartite graphs, a bipartite graph $G$ of order $n$ is called $k$-semibipancyclic, $k\ge 0$, if there is no “gap” of $k+1$ among the even cycle lengths in $G$, i.e., for no $\ell \le n-2k$ is it the case that each of $C_{2\ell },\dots ,C_{2\ell +2k}$ is missing from $G$.

In this paper we generalize a result of Hakimi and Schmeichel in several ways. First to $k$-semipancyclic, then to bipartite graphs, giving a condition for a hamiltonian bipartite graph to be bipancyclic or one of two exceptional graphs. Finally, we give a condition for a hamiltonian bipartite graph to be $k$-semibipancyclic or a member of a very special class of hamiltonian bipartite graphs.