Necessary and Sufficient Conditions for a Hamiltonian Graph

Abstract

A graph is singular if the zero eigenvalue is in the spectrum of its $0-1$ adjacency matrix $A$. If an eigenvector belonging to the zero eigenspace of $A$ has no zero entries, then the singular graph is said to be a core graph. A $(\kappa ,\tau )$-regular set is a subset of the vertices inducing a $\kappa$-regular subgraph such that every vertex not in the subset has $\tau$ neighbors in it. We consider the case when $\kappa =\tau$, which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a $(\kappa ,\kappa )$-regular set, then it is a core graph. By considering the walk matrix, we develop an algorithm to extract $(\kappa ,\kappa )$-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.