Small spectral gap in the combinatorial Laplacian implies Hamiltonian

DOI10.1007/s00026-009-0039-4zbMath1229.05193OpenAlexW2049641124MaRDI QIDQ659809

Steve Butler, Fan R. K. Chung

Publication date: 24 January 2012

Published in: Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00026-009-0039-4

zbMATH Keywords

Hamiltoniancombinatorial Laplacianspectral graph theory

Mathematics Subject Classification ID

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

Related Items (26)

Spectral conditions for traceability of connected claw-free graphs ⋮ Matching number, Hamiltonian graphs and magnetic Laplacian matrices ⋮ Extremal problems on the Hamiltonicity of claw-free graphs ⋮ Hyper-Hamiltonicity in graphs: some sufficient conditions ⋮ Eigenvalues and [a,b‐factors in regular graphs] ⋮ Some sufficient spectral conditions on Hamilton-connected and traceable graphs ⋮ Maximum degree and minimum degree spectral radii of some graph operations ⋮ Distance signless Laplacian spectral radius and Hamiltonian properties of graphs ⋮ Graph toughness from Laplacian eigenvalues ⋮ Spectral radius and Hamiltonian graphs ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree ⋮ Signless Laplacian eigenvalues and circumference of graphs ⋮ Spectral radius and Hamiltonian properties of graphs, II ⋮ Sufficient spectral conditions on Hamiltonian and traceable graphs ⋮ Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs ⋮ Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius ⋮ Spectral radius and Hamiltonicity of graphs ⋮ Regular Turán numbers of complete bipartite graphs ⋮ Spectral radius and Hamiltonian properties of graphs ⋮ Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs ⋮ Spectral radius and Hamiltonicity of graphs with large minimum degree ⋮ A tight lower bound on the matching number of graphs via Laplacian eigenvalues ⋮ Energy conditions for Hamiltonicity of graphs ⋮ Signless Laplacian spectral conditions for Hamiltonicity of graphs ⋮ Spectral condition for Hamiltonicity of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the solution of traveling salesman problems
• Hamiltonian circuits in random graphs
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• Hamilton Circuits and Long Circuits
• Sparse pseudo‐random graphs are Hamiltonian
• The Traveling-Salesman Problem and Minimum Spanning Trees

This page was built for publication: Small spectral gap in the combinatorial Laplacian implies Hamiltonian