Bounds on graph eigenvalues. II (Q2459961)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounds on graph eigenvalues. II |
scientific article |
Statements
Bounds on graph eigenvalues. II (English)
0 references
9 November 2007
0 references
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).]
0 references
clique number
0 references
spectral radius
0 references
Turán graph
0 references
maximum degree
0 references
books
0 references