Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs

DOI10.1016/J.LAA.2016.11.024MaRDI QIDQ501276zbMATH OpenOpenAlexFDO

Authors Bo Ning, Binlong Li

Publication date 29 December 2016

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

Full work available at URL https://arxiv.org/abs/1601.06890

zbMATH Keywords

balanced bipartite graphsHamilton pathMoon-Moser's theoremnearly balanced bipartite graphsspectral analogues

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Paths and cycles (05C38)

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.

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

Cites work

• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3186566 (Why is no real title available?)
• A contribution to the Zarankiewicz problem
• A method in graph theory
• A note on Laplacian graph eigenvalues
• A spectral Erdős-Stone-Bollobás theorem
• Arc coverings of graphs
• Eigenvalues of the Laplacian of a graph^∗
• Hamilton cycles and eigenvalues of graphs
• More spectral bounds on the clique and independence numbers
• On Hamiltonian bipartite graphs
• On the first eigenvalue of bipartite graphs
• On the spectral radii of graphs without given cycles
• On the spectral radius of graphs with cut vertices
• On three conjectures involving the signless Laplacian spectral radius of graphs
• Signless Laplacian spectral radius and Hamiltonicity
• Small spectral gap in the combinatorial Laplacian implies Hamiltonian
• Some new results in extremal graph theory
• Sparse pseudo‐random graphs are Hamiltonian
• Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles
• Spectral conditions for the existence of specified paths and cycles in graphs
• Spectral radius and Hamiltonian graphs
• Spectral radius and Hamiltonian properties of graphs
• Spectral radius and Hamiltonicity of graphs
• Sufficient spectral conditions on Hamiltonian and traceable graphs
• The spectral radius of graphs without paths and cycles of specified length

Cited in

(19)

• Spectral radius and traceability of graphs with large minimum degree
• Spectral radius and \(k\)-connectedness of a graph
• Extremal problems on the Hamiltonicity of claw-free graphs
• Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius
• Spectral radius and Hamiltonian properties of graphs. II
• Spanning bipartite graphs with large degree sum in graphs of odd order
• Unified spectral Hamiltonian results of balanced bipartite graphs and complementary graphs
• Spectral radius and Hamiltonicity of graphs
• Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree
• Sufficient conditions for Hamilton-connected graphs in terms of (signless Laplacian) spectral radius
• Characterizing degree-sum maximal nonhamiltonian bipartite graphs
• Some generalizations of spectral conditions for \(2s\)-Hamiltonicity and \(2s\)-traceability of bipartite graphs
• Spectral radius and rainbow Hamilton paths of a graph
• Extremal problems on distance spectra of graphs
• Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles
• Spectral conditions and Hamiltonicity of a balanced bipartite graph with large minimum degree
• Sufficient spectral conditions for graphs being k-edge-Hamiltonian or k-Hamiltonian
• Spectral conditions for graphs to be \(\beta\)-deficient involving minimum degree
• Some new sufficient conditions for 2p-Hamilton-biconnectedness of graphs

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)