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

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

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)

Cites Work

• Sparse pseudo‐random graphs are Hamiltonian
• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Traveling-Salesman Problem and Minimum Spanning Trees
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hamilton Circuits and Long Circuits

Cited In (29)

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