Small spectral gap in the combinatorial Laplacian implies Hamiltonian

DOI10.1007/S00026-009-0039-4zbMATH Open1229.05193OpenAlexW2049641124MaRDI QIDQ659809FDOQ659809

Authors Steve Butler, Fan 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

spectral graph theoryHamiltoniancombinatorial Laplacian

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5116216
• scientific article; zbMATH DE number 6401583
• Bounds on signless Laplacian eigenvalues of Hamiltonian graphs
• Laplacian spectral radius and some Hamiltonian properties of graphs
• Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius

Cites work

• scientific article; zbMATH DE number 2133152 (Why is no real title available?)
• scientific article; zbMATH DE number 3584645 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Hamilton Circuits and Long Circuits
• Hamiltonian circuits in random graphs
• On the solution of traveling salesman problems
• Sparse pseudo‐random graphs are Hamiltonian
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The searching over separators strategy to solve some NP-hard problems in subexponential time

Cited in

(29)

• Signless Laplacian spectral conditions for Hamiltonicity of graphs
• Hyper-Hamiltonicity in graphs: some sufficient conditions
• Spectral condition for Hamiltonicity of a graph
• Recent advances on the Hamiltonian problem: survey III
• Spectral conditions for traceability of connected claw-free graphs
• Extremal problems on the Hamiltonicity of claw-free graphs
• Regular Turán numbers of complete bipartite graphs
• A tight lower bound on the matching number of graphs via Laplacian eigenvalues
• Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius
• Spectral radius and Hamiltonian properties of graphs. II
• Improved upper bounds on even-cycle creating Hamilton paths
• Energy conditions for Hamiltonicity of graphs
• Matching number, Hamiltonian graphs and magnetic Laplacian matrices
• Spectral radius and Hamiltonian graphs
• Spectral radius and Hamiltonian properties of graphs
• Spectral radius and Hamiltonicity 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 domain monotonicity theorem for graphs and Hamiltonicity
• Signless Laplacian eigenvalues and circumference of graphs
• Sufficient spectral conditions on Hamiltonian and traceable graphs
• Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree
• Maximum degree and minimum degree spectral radii of some graph operations
• Graph toughness from Laplacian eigenvalues
• Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs
• Some sufficient spectral conditions on Hamilton-connected and traceable graphs
• scientific article; zbMATH DE number 5116216 (Why is no real title available?)
• Eigenvalues and [a,b]‐factors in regular graphs
• Distance signless Laplacian spectral radius and Hamiltonian properties of graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659809)