Some Inequalities for the Largest Eigenvalue of a Graph (Q3147278)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1802831
Language Label Description Also known as
default for all languages
No label defined
    English
    Some Inequalities for the Largest Eigenvalue of a Graph
    scientific article; zbMATH DE number 1802831

      Statements

      Some Inequalities for the Largest Eigenvalue of a Graph (English)
      0 references
      0 references
      11 February 2003
      0 references
      adjacency matrix
      0 references
      clique number
      0 references
      It is shown that for a \(K_{p+1}\)-free graph \(G\), the largest eigenvalue \(\lambda(G)\) of its adjacency matrix cannot exceed \(\sqrt{2{p-1\over p} e(G)}\), where \(K_p\) is the complete graph on \(p\) vertices and \(e(G)\) is the number of edges in \(G\). A clique is a complete subgraph. The clique number \(\text{cl}(G)\) of \(G\) is the size of a maximum clique in \(G\). It is shown that if \(T_i\) is the number of all \(i\)-cliques of \(G\), \(\lambda= \lambda(G)\) and \(p= \text{cl}(G)\), then \[ \lambda^p\leq T_2\lambda^{p- 2}+\cdots+ (i-1) T_i\lambda^{p- i}+\cdots+ (p-1) T_p\qquad\text{and} \] \[ \lambda(G)\leq {\delta-1\over 2}+ \sqrt{2e(G)- \delta n+{(\delta+ 1)^2\over 4}}, \] where \(\delta\) is the minimal degree of \(G\).
      0 references

      Identifiers