Bounds on graph eigenvalues I

By Vladimir Nikiforov. 2006

118 citations recorded by the source corpus.

Abstract We prove three results about the spectral radius μ ( G ) of a graph G : (a) Let T r ( n ) be the r -partite Turan graph of order n . If G is a K r + 1 -free graph of order n , then μ ( G ) μ ( T r ( n ) ) unless G = T r ( n ) . (b) For most irregular graphs G of order n and size m , μ ( G ) - 2 m / n > 1 / ( 2 m + 2 n ) . (c) Let 0 ⩽ k ⩽ l . If G is a graph of order n with no K 2 + K ¯ k + 1 and no K 2 , l + 1 , then μ ( G ) ⩽ min G ) , ( k - l + 1 + ( k - l + 1 ) 2 + 4 l ( n - 1 ) ) / 2 } .

Subfields: Computational Theory and Mathematics, Geometry and Topology, Organic Chemistry

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

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. Xiaodong Zhang
2. Ya-Lei Jin
3. Bian He
4. Miklós Simonovits
5. Z. Furedi
6. Vladimir Nikiforov
7. Pierre Hansen
8. Dragan Stevanovic

In Geometry and Topology

1. Xiaodong Zhang
2. Pierre Hansen
3. Mustapha Aouchiche
4. Ya-Lei Jin
5. Bian He
6. Vladimir Nikiforov
7. Miklós Simonovits
8. Z. Furedi

In Organic Chemistry

1. Xiaodong Zhang
2. Mustapha Aouchiche
3. Pierre Hansen
4. Miklós Simonovits
5. Z. Furedi
6. Dragan Stevanovic
7. Vladimir Nikiforov
8. Zoran Stanic

Citations in the corpus

• A spectral condition for odd cycles in graphs (2007, background): “ to contain a cycle of length t for some t ≤ n/321, then G resembles T2 (n). Keywords: odd cycle; triangle; graph spectral radius; stabilty AMS classification: 05C50, 05C35.. Introduction It is known ([5], [7]) that if G is a graph of order n and the largest eigenvalue µ(G) of its adjacency matrix sa”
• The maximum spectral radius of C4-free graphs of given order and size (2007, background): “Theorem 3 in [ 10 ] gives a result more general than just inequality (1):”
• The spectral radius of graphs without paths and cycles of specified length (2009, result): “ ⌊n2/4⌋. Thus, for odd l we have fl (n) ∼ n/2. As we shall see below, this is in sharp contrast with the value of fl (n) for even l. Bounds on f4 (n) The value of f4 (n) was essentially determined in [13]: Let G be a graph of order n with µ(G) = µ. If C4 *G, then µ2 −µ ≤ n− 1. (1) Equality holds if ”
• Sharp Bounds for the Signless Laplacian Spectral Radius in Terms of Clique Number (2012, background): “ved previously by Guiduli [6], but his proof was made public only after the publication of [10]. Further, Nikiforov explicitly advocated the study of general Tura´n problems in many publications (see [10]-[15]). For instance, he determined [13] the maximum spectral radius of graphs without paths of ”
• On the spectral radius of graphs with a given domination number (2007, background): “The maximization part of this problem has been solved for a number of graph classes so far, although it is interesting that it has been solved only recently for the sets of connected graphs which have a given value of some well-known integer graph invariant: for example, the number of cut vertices [”
• The Laplacian eigenvalues of graphs: a survey (2011, background): “Recently, Nikiforov in [77] gave another upper bound.”
• The History of Degenerate (Bipartite) Extremal Graph Problems (2013, background): “Given a Kk+1-free graph Gn Nikiforov [197] showed that Λ(Gn) < λ(Tn,k) unless G = Tn,k.”