The spectral radius of graphs without paths and cycles of specified length

By Vladimir Nikiforov. 2009

219 citations recorded by the source corpus.

Abstract Let G be a graph with n vertices and μ ( G ) be the largest eigenvalue of the adjacency matrix of G . We study how large μ ( G ) can be when G does not contain cycles and paths of specified order. In particular, we determine the maximum spectral radius of graphs without paths of given length, and give tight bounds on the spectral radius of graphs without given even cycles. We also raise a number of open problems.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology

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

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. Yongtao Li
2. Lihua Feng
3. Weijun Liu
4. Xiaodong Zhang
5. Bian He
6. Ya-Lei Jin
7. Dheer Noal Desai
8. Michael Tait

In Geometry and Topology

1. Yongtao Li
2. Xiaodong Zhang
3. Lihua Feng
4. Weijun Liu
5. Ya-Lei Jin
6. Bian He
7. Vladimir Nikiforov
8. Dheer Noal Desai

Citations in the corpus

• Spectral radius and Hamiltonian properties of graphs (2013, unknown): “From [5], we know ρ(Gn,k) = ( k − 1 + √4kn − (3k − 1)(k + 1))/2.”
• 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.”
• Sharp Bounds for the Signless Laplacian Spectral Radius in Terms of Clique Number (2012, background): “For instance, he determined [13] the maximum spectral radius of graphs without paths of given length and presented [15] a comprehensive survey on these topics.”
• A survey on spectral conditions for some extremal graph problems (2021, background): “Finally, Nikiforov [155] characterized the spectral radius of graphs without paths and cycles of specified length.”
• Some new results in extremal graph theory (2011, background): “We do not know the exact value of gl (n) for l > 3; but we have the following theorem from [81].”
• The spectral radius of graphs without long cycles (2017, unknown): “In this paper, a weaker version of Nikiforov’s conjecture is considered, we prove that for a given integer k ≥ 2, any graph G of sufficiently large order n with spectral radius µ(G) ≥ µ(Sn,k) (or µ(G) ≥ µ(S+n,k)) contains a cycle Cℓ with ℓ ≥ 2k+1 (or Cℓ with ℓ ≥ 2k + 2), unless G = Sn,k (or G = S+n,”