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

preprint2016arXivOpen access

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 Gnk\mathcal{G}_n^k be the class of non-Hamiltonian graphs of order nn and minimum degree at least kk. We determine the maximum (signless Laplacian) spectral radius of graphs in Gnk\mathcal{G}_n^k (for large enough nn), and the minimum (signless Laplacian) spectral radius of the complements of graphs in Gnk\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.