Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian |
| |
Authors: | Steve Butler Fan Chung |
| |
Institution: | 1. Department of Mathematics, University of California, Los Angeles, CA, 90095-1555, USA 2. Department of Mathematics, University of California, San Diego, La Jolla, CA, 92093-0112, USA
|
| |
Abstract: | 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 is given for the problem of finding a Hamiltonian cycle in graphs with
bounded spectral gaps which has complexity of order n
cln n
. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|