Prefer a chat interface with context about you and your work?
Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian
We consider the spectral and algorithmic aspects of the problem of finding a Hamiltonian cycle in a graph. We show that a sufficient condition for a graph being Hamiltonian is that the nontrivial eigenvalues of the combinatorial Laplacian are sufficiently close to the average degree of the graph. An algorithm …