Spectral radius and Hamiltonicity of graphs

By Miroslav Fiedler, Vladimir Nikiforov. 2009

152 citations recorded by the source corpus.

Abstract Let G be a graph of order n and μ ( G ) be the largest eigenvalue of its adjacency matrix. Let G ¯ be the complement of G . Write K n - 1 + v for the complete graph on n - 1 vertices together with an isolated vertex, and K n - 1 + e for the complete graph on n - 1 vertices with a pendent edge. We show that: If μ ( G ) ⩾ n - 2 , then G contains a Hamiltonian path unless G = K n - 1 + v ; if strict inequality holds, then G contains a Hamiltonian cycle unless G = K n - 1 + e . If μ ( G ¯ ) ⩽ n - 1 , then G contains a Hamiltonian path unless G = K n - 1 + v . If μ ( G ¯ ) ⩽ n - 2 , then G contains a Hamiltonian cycle unless G = K n - 1 + e .

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/b3f4b15a72182f8439ed2b231472e25392c2f5d3

How researchers see this paper

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

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Spectral radius and Hamiltonian properties of graphs (2013, background): “Theorem 3 (Fiedler and Nikiforov [2]) Let G be a graph on n vertices.”
A survey on spectral conditions for some extremal graph problems (2021, background): “In 2015, Ning and Ge [160] refined the extremal result of Ore and the spectral result of Fiedler and Nikiforov for graphs with minimum degree at least two.”
Spectral analogues of Erdős’ and Moon–Moser’s theorems on Hamilton cycles (2015, background): “Fiedler and Nikiforov’s theorems can be seen as spectral analogues of Ore’s theorem.”
Spectral radius and Hamiltonicity of graphs with large minimum degree (2016, background): “In 2010, Fiedler and Nikiforov [9] gave some bounds on λ (G) implying the existence of Hamiltonian paths and ∗Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA cycles in G.”
Spectral extremal graphs for intersecting cliques (2021, background): “In addition, Fiedler and Nikiforov [16] obtained tight sufficient conditions for graphs to be Hamiltonian or traceable.”
Spectral radius and Hamiltonian graphs (2012, background): “Other spectral conditions for Hamiltonian cycles or Hamiltonian paths have been given in [3,6,8,13,15].”
Some new results in extremal graph theory (2011, background): “In [11], using interlacing, Bollobás and Nikiforov gave the following inequality, which has been used to prove several results involving the minimum eigenvalue of the adjacency matrix, e.g., Theorem 3.22.”