Divergence Condition for Pancyclicity

Abstract

Let $G$ be a connected graph and let $u$ and $v$ be two vertices of $G$ such that $d_G(u,v)=2$. We define their divergence to be: ${\alpha }^{\ast }(u,v)=\underset{w}{max}\{|S|\mid$ for each $w\in N_G(u)\cap N_G(v),S$ is a maximum independent set in $N_G(w)$ containing $u\text{ and }v\}.$ It is proved that if for each pair of vertices $u$ and $v$ of $G$ such that $d_G(u,v)=2$, $|N_G(u)\cap N_G(v)|\ge {\alpha }^{\ast }(u,v)$ and if $\nu (G)\ge 3$, then $G$ is pancyclic unless $G$ is $K_{\nu /2,\nu /2}$. Several previously known sufficient conditions for pancyclicity follow as corollaries.