Spectral analogues of Erdős’ and Moon–Moser’s theorems on Hamilton cycles

By Binlong Li, Bo Ning. 2015

96 citations recorded by the source corpus.

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 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 (for large enough n), and the minimum (signless Laplacian) spectral radius of the complements of graphs in . 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.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/659d7ab96d7c1707f7c28659b12e66e05f7ad7f7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

  1. Weijun Liu
  2. Yongtao Li
  3. Lihua Feng

In Geometry and Topology

  1. Weijun Liu
  2. Yongtao Li
  3. Lihua Feng

Citations in the corpus