Stability, Total Vertices, and Hamiltonian Cycles

Abstract

A known theorem of Bigalke and Jung says that the only nonhamiltonian, tough graph $G$ with $\alpha (G)\le H(G)+1$, where $H(G)\ge 3$, is the Petersen graph. In this paper we characterize all nonhamiltonian, tough graphs having k total vertex (i.e. adjacent to all others) with $\alpha (G)\le k+2$ (Theorem 3).