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 (κ, τ)-regular set is a subset of the vertices inducing a κ-regular subgraph such that every vertex not in the subset has τ neighbours in it. We consider the case when κ = τ which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a (κ, κ)-regular set, then it is a core graph. By considering the walk matrix we develop an algorithm to extract (κ, κ)-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.