Detecting Hamiltonian cycles

摘要

We present some conditions equivalent to the existence of a Hamiltonian cycle in a graph on n vertices. Among other things, we show that for each n, there is an explicitly determined n×n diagonal matrix D such that if A is the adjacency matrix of such a graph, then the existence of a Hamiltonian cycle is completely determined by the eigenvalues of AD. These results have some bearing on possible algorithms which detect such cycles, and we discuss this.