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

TLDR

Erdős provided a sufficient condition for Hamilton cycles in terms of vertex count, edge count, and minimum degree, extending Ore's theorem, and Moon and Moser later established a similar result for balanced bipartite graphs. This paper presents spectral analogues of Erdős' theorem and Moon–Moser's theorem. The authors analyze non‑Hamiltonian graphs of order n with minimum degree at least k, determining the maximum signless Laplacian spectral radius for large n and the minimum spectral radius of their complements, and extend these results to balanced bipartite graphs and quasi‑complements. They identify all extremal graphs achieving the maximum signless Laplacian spectral radius and the minimum spectral radius of the complements, and similarly characterize the extremal graphs for the bipartite and quasi‑complement cases.

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 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.