<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian
Steve Butler1 and Fan Chung2
1Department of Mathematics, University of California, Los Angeles, CA 90095-1555, USA
sbutler@math.ucsd.edu
2Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA
fan@math.ucsd.edu
Annals of Combinatorics 13 (4) pp.403-412 December, 2009
AMS Subject Classification: 05C45
Abstract:
We consider the spectral and algorithmic aspects of the problem of nding 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 ncln n.
Keywords: Hamiltonian, combinatorial Laplacian, spectral graph theory

References:

1. Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd Ed. Wiley, New York (2000)

2. Applegate, D., Bixby, R., Chv´atal, V., Cook, W.: On the solution of traveling salesman problems. Doc. Math. 3, 645–--656 (1998)

3. Chang, H.-W., Hwang, F.K., Lee, J.S.: The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica 9, 398--–423 (1993)

4. Chung, F.: Discrete isoperimetric inequalities. In: Surveys in Differential Geometry, vol. IX, pp. 53–82. International Press, Somerville (2004)

5. Dirac, G.A.: Hamiltonian circuits and long circuits. Ann. Discrete Math. 3, 75–92 (1978)

6. Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Operation Res. 18, 1138--–1162 (1970)

7. Karp, R.M.: Reduciblity among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Comoplexity of Computer Computations, pp. 85--–103. Plenum, New York (1972)

8. Komlós, J., Szemerédi, E.: Hamilton cycles in random graphs. In: Infinite and finite sets, vol. II, pp. 1003--–1010. North-Holland, Amsterdam (1975)

9. Krivelevich, M., Sudakov, B.: Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory 42, 17--–33 (2003)

10. Pósa, L.: Hamiltonian circuits in random graphs. Discrete Math. 14, 359--–364 (1976)

11. Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization—Eureka, You shrink!, pp. 18--5–207. Springer, New York (2003)