Hamilton cycles and eigenvalues of graphs

DOI10.1016/0024-3795(95)00254-OMaRDI QIDQ1899443zbMATH OpenWikidataFDO

Authors Jan van den Heuvel

Publication date 29 September 1996

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(95)00254-O

zbMATH Keywords

eigenvaluesHamiltonian cycleHamiltonian graphLaplacian matrixPetersen graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Review text

The author derives some inequalities for the eigenvalues of the Laplacian matrix (and of a related matrix) of a Hamiltonian graph. This enables an eigenvalue proof of the non-existence of a Hamiltonian cycle for some graphs (in particular, for the Petersen graph).

Recommendations

• A domain monotonicity theorem for graphs and Hamiltonicity
• Bounds on signless Laplacian eigenvalues of Hamiltonian graphs
• Energy and Hamiltonicity of graphs
• Detecting Hamiltonian cycles
• Spectral results on some Hamiltonian properties of graphs

Cites work

• A characterization of the smallest eigenvalue of a graph
• A domain monotonicity theorem for graphs and Hamiltonicity
• Graph theory
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• scientific article; zbMATH DE number 867649 (Why is no real title available?)
• Laplacian matrices of graphs: A survey
• Problems in algebraic combinatorics
• Toughness, hamiltonicity and split graphs

Cited in

(57)

• On Hamiltonian cycles and Hamiltonian paths
• Hamilton cycles in Euler tour graphs
• Detecting Hamiltonian cycles
• A domain monotonicity theorem for graphs and Hamiltonicity
• Some properties of the spectrum of graphs
• Extremal problems on the Hamiltonicity of claw-free graphs
• On the least Q-eigenvalue of a non-bipartite Hamiltonian graph
• Automated conjecturing. III. Property-relations conjectures
• The Laplacian spectrum of a graph
• Interlacing eigenvalues and graphs
• An interlacing technique for spectra of random walks and its application to finite percolation clusters
• On the least signless Laplacian eigenvalue of a non-bipartite connected graph with fixed maximum degree
• The Laplacian spread of line graphs
• Spectral radius and the 2-power of Hamilton cycle
• Spectral preorder and perturbations of discrete weighted graphs
• Matching number, Hamiltonian graphs and magnetic Laplacian matrices
• Maxima of the Laplacian spectral radius of (minimally) 2-connected graphs with fixed size
• \(Q\)-integral graphs with at most two vertices of degree greater than or equal to three
• Signless Laplacian eigenvalue problems of Nordhaus-Gaddum type
• The quasi-tree graph with maximum Laplacian spread
• Open problem on \(\sigma\)-invariant
• On the spectrum of the normalized Laplacian for signed graphs: interlacing, contraction, and replication
• Recent advances on the Hamiltonian problem: survey III
• On incidence energy of graphs
• Signless Laplacian eigenvalues and circumference of graphs
• Spectral condition for Hamiltonicity of a graph
• Maximum degree and minimum degree spectral radii of some graph operations
• The (signless) Laplacian spectral radius of unicyclic and bicyclic graphs with \(n\) vertices and \(k\) pendant vertices
• Eigenspaces of Hamming graphs and unitary Cayley graphs
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Spectral radius and Hamiltonian graphs
• Some graphs determined by their (signless) Laplacian spectra.
• Eigenvalue ratios of non-negatively curved graphs
• Spectral radius and Hamiltonian properties of graphs
• Laplacian and signless Laplacian spectral radii of graphs with fixed domination number
• Eigenvalues and triangles in graphs
• Traversing every edge in each direction once, but not at once: cubic (polyhedral) graphs
• Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs
• Laplacian integral graphs with a given degree sequence constraint
• On a conjecture involving the second largest signless Laplacian eigenvalue and the index of graphs
• Spectral conditions for some graphical properties
• Energy and Hamiltonicity of graphs
• Proof of conjecture involving the second largest signless Laplacian eigenvalue and the index of graphs
• Nordhaus-Gaddum-type result on the second largest signless Laplacian eigenvalue of a graph
• Spectral radius and Hamiltonicity of graphs
• Spectral dynamics of guided edge removals and identifying transient amplifiers for death-birth updating
• Multiplicity of signless Laplacian eigenvalue 2 of a connected graph with a perfect matching
• Which Laplacian cospectral graphs have the same degree sequences?
• Upper bounds on the second largest Laplacian eigenvalue of graphs with given size
• Determining some graph joins by the signless Laplacian spectrum
• Two classes of graphs determined by the signless Laplacian spectrum
• Signless Laplacian characterization of cones over disjoint unions of cycles, edges and isolated vertices
• Maximum Laplacian energy of unicyclic graphs
• Proof of conjectures involving the largest and the smallest signless Laplacian eigenvalues of graphs
• Graph homomorphisms and nodal domains
• Relation between signless Laplacian energy, energy of graph and its line graph
• On conjectures involving second largest signless Laplacian eigenvalue of graphs

This page was built for publication: Hamilton cycles and eigenvalues of graphs

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