Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs
From MaRDI portal
Publication:501276
DOI10.1016/J.LAA.2016.11.024zbMATH Open1352.05116arXiv1601.06890OpenAlexW2264398285MaRDI QIDQ501276FDOQ501276
Authors: Bo Ning, Binlong Li 
Publication date: 29 December 2016
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: In 1962, ErdH{o}s proved a theorem on the existence of Hamilton cycles in graphs with given minimum degree and number of edges. Significantly strengthening in case of balanced bipartite graphs, Moon and Moser proved a corresponding theorem in 1963. In this paper we establish several spectral analogues of Moon and Moser's theorem on Hamilton paths in balanced bipartite graphs and nearly balanced bipartite graphs. One main ingredient of our proofs is a structural result of its own interest, involving Hamilton paths in balanced bipartite graphs with given minimum degree and number of edges.
Full work available at URL: https://arxiv.org/abs/1601.06890
Recommendations
- Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles
- Spectral radius and Hamiltonian properties of graphs. II
- Spectral radius of a balanced bipartite graph and its Hamiltonicity
- Spectral analogues of Erdős' theorem on Hamilton-connected graphs
- Characterizing degree-sum maximal nonhamiltonian bipartite graphs
balanced bipartite graphsHamilton pathMoon-Moser's theoremnearly balanced bipartite graphsspectral analogues
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Paths and cycles (05C38)
Cites Work
- More spectral bounds on the clique and independence numbers
- Signless Laplacian spectral radius and Hamiltonicity
- A note on Laplacian graph eigenvalues
- Hamilton cycles and eigenvalues of graphs
- Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles
- On the spectral radii of graphs without given cycles
- Eigenvalues of the Laplacian of a graph∗
- Spectral radius and Hamiltonian graphs
- Sufficient spectral conditions on Hamiltonian and traceable graphs
- Sparse pseudo‐random graphs are Hamiltonian
- Spectral radius and Hamiltonian properties of graphs
- Spectral radius and Hamiltonicity of graphs
- Small spectral gap in the combinatorial Laplacian implies Hamiltonian
- The spectral radius of graphs without paths and cycles of specified length
- On the spectral radius of graphs with cut vertices
- Some new results in extremal graph theory
- A spectral Erdős-Stone-Bollobás theorem
- A contribution to the Zarankiewicz problem
- On the first eigenvalue of bipartite graphs
- Title not available (Why is that?)
- A method in graph theory
- On Hamiltonian bipartite graphs
- Title not available (Why is that?)
- On three conjectures involving the signless Laplacian spectral radius of graphs
- Arc coverings of graphs
- Spectral conditions for the existence of specified paths and cycles in graphs
Cited In (19)
- Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree
- Spectral radius and Hamiltonicity of graphs
- Spectral radius and rainbow Hamilton paths of a graph
- Unified spectral Hamiltonian results of balanced bipartite graphs and complementary graphs
- Spectral conditions for graphs to be \(\beta\)-deficient involving minimum degree
- Spectral conditions and Hamiltonicity of a balanced bipartite graph with large minimum degree
- Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles
- Sufficient spectral conditions for graphs being k-edge-Hamiltonian or k-Hamiltonian
- Some generalizations of spectral conditions for \(2s\)-Hamiltonicity and \(2s\)-traceability of bipartite graphs
- Extremal problems on distance spectra of graphs
- Extremal problems on the Hamiltonicity of claw-free graphs
- Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius
- Some new sufficient conditions for 2p-Hamilton-biconnectedness of graphs
- Spanning bipartite graphs with large degree sum in graphs of odd order
- Sufficient conditions for Hamilton-connected graphs in terms of (signless Laplacian) spectral radius
- Spectral radius and \(k\)-connectedness of a graph
- Spectral radius and Hamiltonian properties of graphs. II
- Characterizing degree-sum maximal nonhamiltonian bipartite graphs
- Spectral radius and traceability of graphs with large minimum degree
This page was built for publication: Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501276)
