Bounds on graph eigenvalues II

By Vladimir Nikiforov. 2006

250 citations recorded by the source corpus.

We prove three results about the spectral radius μ(G) of a graph G: (a) Let Tr (n) be the r-partite Turán graph of order n. If G is a Kr+1-free graph of order n, then μ(G) < μ(Tr (n)) unless G = Tr (n). (b) For most irregular graphs G of order n and size m, μ(G) − 2m/n > 1/(2m + 2n). (c) Let 0 k l. If G is a graph of order n with no K2 + Kk+1 and no K2,l+1, then μ(G) min { (G), ( k − l + 1 + √ (k − l + 1)2 + 4l(n − 1) )/ 2 } . © 2007 Elsevier Inc. All rights reserved. AMS classification: Primary 05C50; Secondary 05C35

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

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

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

1. Yongtao Li
2. Xiaodong Zhang
3. Lihua Feng
4. Weijun Liu
5. Ya-Lei Jin
6. Bian He
7. Miklós Simonovits
8. Z. Furedi

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. Miklós Simonovits

Citations in the corpus

• Sharp Bounds for the Signless Laplacian Spectral Radius in Terms of Clique Number (2012, background): “Nikiforov [10] proved a spectral extremal Turán theorem: let λ(G) be the largest eigenvalues of the adjacency matrix of G not containing complete graph Kt of order t as a subgraph, then λ(G) ≤ λ(Tn,t−1) with equality if and only if G = Tn,t−1; the same result has been proved previously by Guiduli [6”
• The History of Degenerate (Bipartite) Extremal Graph Problems (2013, background): “We have already mentioned Nikiforov’s result (Theorem 3.21) on the Zarankiewicz problem.”
• Some new results in extremal graph theory (2011, methodology): “Similar inequalities [72] exist also for the Laplacian eigenvalues.”
• A survey on spectral conditions for some extremal graph problems (2021, background): “Soon after, Nikiforov [147] showed that if G is a Kr+1-free graph on n vertices, then λ(G) ≤ λ(Tr(n)), equality holds if and only if G = Tr(n).”
• The maximum spectral radius of C4-free graphs of given order and size (2007, background): “How large can μ (G) be if G has no cycles of length 4? This question was partially answered in [10], Theorem 3: Let G be a graph of order n with μ (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.”
• A contribution to the Zarankiewicz problem (2009, unknown): “Proof of Theorem 1 Inequality (1) has been proved in [9], so we shall assume that s ≥ 3 and t ≥ 3.”
• A spectral condition for odd cycles in graphs (2007, background): “It is known ([9], [14]) that if G is a graph of order n and the largest eigenvalue μ (G) of its adjacency matrix satisfies μ (G) > √ ⌊n2/4⌋, then a triangle exists in G.”
• The spectral radius of graphs without paths and cycles of specified length (2009, background): “Bounds on f4 (n) The value of f4 (n) was essentially determined in [13]: Let G be a graph of order n with μ (G) = μ.”