On Hamiltonicity of regular graphs with bounded second neighborhoods

Abstract

Let $\mathcal{G}(k)$ denote the set of connected $k$-regular graphs $G$, $k\ge 2$, where the number of vertices at distance 2 from any vertex in $G$ does not exceed $k$. Asratian (2006) showed (using other terminology) that a graph $G\in \mathcal{G}(k)$ is Hamiltonian if for each vertex $u$ of $G$ the subgraph induced by the set of vertices at distance at most 2 from $u$ is 2-connected. We prove here that in fact all graphs in the sets $\mathcal{G}(3)$, $\mathcal{G}(4)$ and $\mathcal{G}(5)$ are Hamiltonian. We also prove that the problem of determining whether there exists a Hamilton cycle in a graph from $\mathcal{G}(6)$ is NP-complete. Nevertheless we show that every locally connected graph $G\in \mathcal{G}(k)$, $k\ge 6$, is Hamiltonian and that for each non-Hamiltonian cycle $C$ in $G$ there exists a cycle $C^{\prime }$ of length $|V(C)|+\ell$ in $G$, $\ell \in \{1,2\}$, such that $V(C)\subset V(C^{\prime })$. Finally, we note that all our conditions for Hamiltonicity apply to infinitely many graphs with large diameters.

19 pages, 6 figures