Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles

Abstract

In 1962, Erdős gave a sufficient condition for Hamilton cycles in terms of the vertex number, edge number, and minimum degree of graphs which generalized Ore's theorem. One year later, Moon and Moser gave an analogous result for Hamilton cycles in balanced bipartite graphs. In this paper we present the spectral analogues of Erdős' theorem and Moon-Moser's theorem, respectively. Let ${\mathcal{G}}_n^k$ be the class of non-Hamiltonian graphs of order $n$ and minimum degree at least $k$. We determine the maximum (signless Laplacian) spectral radius of graphs in ${\mathcal{G}}_n^k$ (for large enough $n$), and the minimum (signless Laplacian) spectral radius of the complements of graphs in ${\mathcal{G}}_n^k$. All extremal graphs with the maximum (signless Laplacian) spectral radius and with the minimum (signless Laplacian) spectral radius of the complements are determined, respectively. We also solve similar problems for balanced bipartite graphs and the quasi-complements.

21 pages; 3 figures; to appear in Linear and Multilinear Algebra

Cited by in corpus (22)

• Eigenvalues and triangles in graphs
• Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs
• Wiener index, Harary index and Hamiltonicity of graphs
• The formula for Turán number of spanning linear forests
• Spectral radius and Hamiltonian properties of graphs, II
• Stability results on the circumference of a graph
• Spectral radius and traceability of connected claw-free graphs
• Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree
• Extremal problems on the Hamiltonicity of claw-free graphs
• The stability method, eigenvalues and cycles of consecutive lengths
• A variation of a theorem by Pósa
• Some Turán-type results for the signless Laplacian spectral radius
• A tight $Q$-index condition for a graph to be $k$-path-coverable involving minimum degree
• Stability in Bondy's theorem on paths and cycles
• Sufficient spectral conditions for graphs being $k$-edge-Hamiltonian or $k$-Hamiltonian
• Some Sufficient Conditions on Pancyclic Graphs
• Wiener Index, Hyper-wiener Index, Harary Index and Hamiltonicity of graphs
• Unified spectral hamiltonian results of balanced bipartite graphs and complementary graphs
• The degrees, number of edges, spectral radius and weakly Hamilton-connectedness of bipartite graphs
• Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree
• Some new sufficient conditions for $2p$-Hamilton-biconnectedness of graphs
• Spectral Conditions for the Bipancyclic Bipartite Graphs