The smallest eigenvalue of K_r-free graphs

DOI10.1016/J.DISC.2006.01.014MaRDI QIDQ2488937zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov

Publication date 16 May 2006

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Graph eigenvalueIndependence numberSecond eigenvalueSmallest eigenvalue

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We give an upper bound on the smallest eigenvalue of the adjacency matrix of graphs with no p-cliques.

Review text

Let \(G\) be a \(K_{r+1}\)-free graph of order \(n\) and size \(m\) with \(r\geq 2\). The author proves \[ \lambda_n(G)<-\frac{2^{r+1}m^r}{rn^{2r-1}}, \] where \(\lambda_n(G)\) is the smallest eigenvalue of the adjacency matrix of \(G\). This implies that if \(G\) is a \(d\)-regular graph of order \(n\) and independence number \(r\), then the second eigenvalue satisfies \[ \lambda_2(G)\geq -1+\frac{2}{r}\frac{(n-1-d)^r}{n^{r-1}}. \]

Recommendations

• Graphs and Hermitian matrices: eigenvalue interlacing
• Eigenvalues and forbidden subgraphs. I.
• Bounds of eigenvalues of \(K_{3,3}\)-minor free graphs
• Regular graphs with small second largest eigenvalue
• On graphs whose smallest eigenvalue is at least \(-1-\sqrt 2\)

Cites work

• Graphs and Hermitian matrices: eigenvalue interlacing
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• Quasi-random graphs
• Some Inequalities for the Largest Eigenvalue of a Graph
• Triangle factors in sparse pseudo-random graphs

Cited in

(19)

• The maximum spectral radius of C₄-free graphs of given order and size
• Bounds of eigenvalues of \(K_{3,3}\)-minor free graphs
• More spectral bounds on the clique and independence numbers
• The least eigenvalue of a graph with a given domination number
• A sharp lower bound for the spectral radius in \(K_4\)-saturated graphs
• The minimum spectral radius of \(K_{r + 1}\)-saturated graphs
• On the partition associated to the smallest eigenvalues of the k-point fixing graph
• Dimension-free bounds and structural results in communication complexity
• New upper bounds on the spectral radius of graphs
• Connected \((K_4 - e)\)-free graphs whose second largest eigenvalue does not exceed 1
• New results for MaxCut in H$H$‐free graphs
• Bounds for A_α-eigenvalues
• A lower bound for the smallest eigenvalue of a graph and an application to the associahedron graph
• Combinatorial upper bounds for the smallest eigenvalue of a graph
• Graphs with large clique number whose second largest eigenvalue does not exceed \((\sqrt{5}-1)/2\)
• On the sum of the largest and smallest eigenvalue of odd-cycle free fraphs
• Eigenvalues and forbidden subgraphs. I.
• Graphs for which the least eigenvalue is minimal. I
• A simpler characterization of a spectral lower bound on the clique number

This page was built for publication: The smallest eigenvalue of \(K_{r}\)-free graphs

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