Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T00:39:17.435Z Has data issue: false hasContentIssue false
  • English
  • Français

Some Inequalities for the Largest Eigenvalue of a Graph

Published online by Cambridge University Press:  25 April 2002

V. NIKIFOROV
V. NIKIFOROV
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee, TN 38152, USA (e-mail: vlado-nikiforov@hotmail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let λ(G) be the largest eigenvalue of the adjacency matrix of a graph G: We show that if G is Kp+1-free then

This inequality was first conjectured by Edwards and Elphick in 1983 and supersedes a series of previous results on upper bounds of λ(G).

Let Ti denote the number of all i-cliques of G, λ = λ(G) and p = cl(G): We show

Let δ be the minimal degree of G. We show

This inequality supersedes inequalities of Stanley and Hong. It is sharp for regular graphs and for a class of graphs which are in some sense maximally irregular.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 2 , March 2002 , pp. 179 - 189
Copyright
2002 Cambridge University Press