# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
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 05C85 Graph algorithms (graph theory)
Full Text:
##### 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