Bounds on graph eigenvalues. II

DOI10.1016/J.LAA.2007.07.010MaRDI QIDQ2459961zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov

Publication date 9 November 2007

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0612461

zbMATH Keywords

booksclique numbermaximum degreespectral radiusTurán graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Some recent results on graph eigenvalues are improved. In particular, among all graphs of given order with no cliques of order $(r+1)$ the $r$-partite Turan graph has maximal spectral radius.

Review text

The author obtains different bounds on the spectral radius of the adjacency matrix of a graph \(G\) of order \(n\) and size \(m\). \(\mu(G)\) denote the maximum eigenvalue of the adjacency matrix of \(G\), \(T_r(n)\) the \(r\)-partite Turán graph of order \(n\), and \(\Delta\) the maximum degree of \(G\). Firstly, the author proves that if \(G\) is a \(K_{r+1}\)-free graph, then \(\mu(G) < \mu(T_r(n)) \) unless \(G=T_r(n)\). If \(G\) is an irregular graph he also shows that \(\mu(G)-2m/n > 1/(2m+2n) \) unless \(G\) is subregular. In this case, \(\mu(G)-2m/n > 1/(n\Delta+2n)\). Finally, the author shows that if \(G\) is a graph with no \(K_2+\overline{K_{k+1}}\) and no \(K_{2,l+1}\), with \(0 \leq k \leq l\), then \[ \mu(G) \leq \min \left\{ \Delta, \frac{k-l+1+\sqrt{(k-l+1)^2+4l(n-1)}}{2} \right\}. \] [For Part I see Linear Algebra Appl. 420, 667--671 (2007; Zbl 1109.05073).]

Recommendations

• Bounds on graph eigenvalues. I
• Upper bounds on the spectral radius of book-free and/or \(K_{2,l}\)-free graphs
• Bounds on graph spectra
• Eigenvalues and forbidden subgraphs. I.
• The spectral radius of irregular graphs

Cites work

• Eigenvalues and degree deviation in graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3214389 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• Large matchings from eigenvalues
• Some Inequalities for the Largest Eigenvalue of a Graph
• Spectral bounds for the clique and independence numbers of graphs
• Spectral radii of graphs with given chromatic number
• Spectral Radius and Degree Sequence
• Spektren endlicher Grafen
• Upper bounds on the spectral radius of book-free and/or \(K_{2,l}\)-free graphs

Cited in

(only showing first 100 items - show all)

• The maximum spectral radius of C₄-free graphs of given order and size
• The minimum spectral radius of graphs with a given independence number
• More spectral bounds on the clique and independence numbers
• Bounds on eigenvalues and chromatic numbers
• Bounds on special subsets in graphs, eigenvalues and association schemes
• Bounds on the greatest eigenvalue of graphs.
• The signless Laplacian spectral radius of \(k\)-connected irregular graphs
• The \(A_{\alpha}\) spectral radius characterization of some digraphs
• Spectral extremal results with forbidding linear forests
• Eigenvalues of subgraphs of the cube
• Computing the \(p\)-spectral radii of uniform hypergraphs with applications
• On the irregularity of uniform hypergraphs
• Sharp lower bounds on the spectral radius of uniform hypergraphs concerning degrees
• On the signless Laplacian spectral radius of irregular graphs
• Extremal spectral radius of \(K_{3,3}/K_{2,4}\)-minor free graphs
• The extremal \(\alpha \)-index of graphs with no 4-cycle and 5-cycle
• Measure-theoretic bounds on the spectral radius of graphs from walks
• A note on spectral radius and degree deviation in graphs
• Spectral extremal results for hypergraphs
• Spectral radius and the 2-power of Hamilton cycle
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles
• A sharp lower bound for the spectral radius in \(K_4\)-saturated graphs
• Spectral extremal graphs for intersecting cliques
• The spectral radius of graphs with no intersecting odd cycles
• Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals
• A spectral condition for the existence of the square of a path
• A unique characterization of spectral extrema for friendship graphs
• Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
• The spectral Turán problem about graphs with no 6-cycle
• The minimum spectral radius of \(K_{r + 1}\)-saturated graphs
• The maximum spectral radius of graphs without friendship subgraphs
• Extremal problems on distance spectra of graphs
• Adjacency eigenvalues of graphs without short odd cycles
• A spectral condition for odd cycles in non-bipartite graphs
• Proof of a conjecture involving the second largest \(D\)-eigenvalue and the number of triangles
• Spectral conditions for the existence of specified paths and cycles in graphs
• The \(\alpha\)-spectral radius of uniform hypergraphs concerning degrees and domination number
• The first few unicyclic and bicyclic hypergraphs with largest spectral radii
• The spectral radius of graphs with no \(k_{2,t}\) minor
• On minimally 2-(edge)-connected graphs with extremal spectral radius
• Spectral radius of digraphs with given dichromatic number
• A spectral condition for odd cycles in graphs
• On the spectral radius of graphs with a given domination number
• Extremal digraphs with given clique number
• On the spectral radius of graphs without a star forest
• The maximum spectral radius of wheel-free graphs
• Maxima of the \(Q\)-index: graphs with no \(K_{1,t}\)-minor
• On a conjecture of spectral extremal problems
• The maximum spectral radius of graphs without spanning linear forests
• Spectral extremal graphs for disjoint cliques
• Stability of Woodall's theorem and spectral conditions for large cycles
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• Quotient of spectral radius, (signless) Laplacian spectral radius and clique number of graphs.
• On a poset of trees. II
• Graphs with small independence number minimizing the spectral radius
• On the spectral moment of graphs with given clique number
• The Laplacian spectral radius of graphs
• Some Bond Graph Structural Properties: Eigen Spectra and Stability
• Sharp bounds for the signless Laplacian spectral radius in terms of clique number
• Extremal problems for the p-spectral radius of graphs
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs
• scientific article; zbMATH DE number 810358 (Why is no real title available?)
• Spectral radius on linear \(r\)-graphs without expanded \(K_{r+1}\)
• The sharp lower bound for the spectral radius of connected graphs with the independence number
• Distance Laplacian eigenvalues and chromatic number in graphs
• On a poset of trees
• Eigenvalue bounds for some classes of matrices associated with graphs
• New results on -spectral radius of graphs
• Maxima of the \(Q\)-index: graphs with no \(K_{s,t}\)
• Spectral extrema of graphs with bounded clique number and matching number
• The maximum spectral radius of \(\{C_3, C_5\}\)-free graphs of given size
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• Disproof of a conjecture on the minimum spectral radius and the domination number
• On a generalization of the spectral Mantel's theorem
• Spectral extremal graphs for the bowtie
• A Spectral Erdős-Sós Theorem
• The sum of the \(k\) largest distance eigenvalues of graphs
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• Refinement on Spectral Turán’s Theorem
• On the irregularity of uniform hypergraphs
• Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
• Maxima of the \(Q\)-index of non-bipartite graphs: forbidden short odd cycles
• An \(A_\alpha\)-spectral Erdős-Pósa theorem
• On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles
• Two spectral extremal results for graphs with given order and rank
• The spectral radius, maximum average degree and cycles of consecutive lengths of graphs
• The unique spectral extremal graph for intersecting cliques or intersecting odd cycles
• Maximum degree and spectral radius of graphs in terms of size
• The index of signed graphs with forbidden subgraphs
• Sharp bounds on the \(A_{\alpha}\)-index of graphs in terms of the independence number
• Extremal results for \(C_3^-\)-free signed graphs
• Spectral extrema of \(\{ K_{k + 1}, \mathcal{L}_s \}\)-free graphs
• Spectral Turán problems for intersecting even cycles
• A spectral extremal problem on non-bipartite triangle-free graphs
• Spectral radius of graphs with given size and odd girth
• Spectral extremal problem on disjoint color-critical graphs
• An \(A_{\alpha}\)-spectral Erdős-Sós theorem
• On the spectral radius of graphs with given maximum degree and girth
• A spectral Erdős-Rademacher theorem

This page was built for publication: Bounds on graph eigenvalues. II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2459961)