×

Small spectral gap in the combinatorial Laplacian implies Hamiltonian. (English) Zbl 1229.05193

Summary: 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^{c\ln n}\).

MSC:

05C45 Eulerian and Hamiltonian graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon N., Spencer J.H.: The Probabilistic Method, 2nd Ed. Wiley, New York (2000) · Zbl 0996.05001
[2] Applegate D., Bixby R., Chvátal V., Cook W.: On the solution of traveling salesman problems. Doc. Math. 3, 645–656 (1998) · Zbl 0904.90165
[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) · Zbl 0797.68161 · doi:10.1007/BF01228511
[4] Chung, F.: Discrete isoperimetric inequalities. In: Surveys in Differential Geometry, vol. IX, pp. 53–82. International Press, Somerville (2004) · Zbl 1067.53025
[5] Dirac G.A.: Hamiltonian circuits and long circuits. Ann. Discrete Math. 3, 75–92 (1978) · Zbl 0376.05035 · doi:10.1016/S0167-5060(08)70499-0
[6] Held M., Karp R.M.: The traveling-salesman problem and minimum spanning trees. Operation Res. 18, 1138–1162 (1970) · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[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) · Zbl 0375.60018
[9] Krivelevich M., Sudakov B.: Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory 42, 17–33 (2003) · Zbl 1028.05059 · doi:10.1002/jgt.10065
[10] Pósa L.: Hamiltonian circuits in random graphs. Discrete Math. 14, 359–364 (1976) · Zbl 0322.05127 · doi:10.1016/0012-365X(76)90068-6
[11] Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization–Eureka, You shrink!, pp. 185–207. Springer, New York (2003) · Zbl 1024.68529
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.