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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references