The Largest Eigenvalue and Bi-Average Degree of a Graph

Details The Largest Eigenvalue and Bi-Average Degree of a Graph The Largest Eigenvalue and Bi-Average Degree of a Graph

2011-06-04

arxiv.org/abs/1106.0811v1

Mathematics

Combinatorics

Scientific paper

We show that for a graph $G$ with the vertex set $V$ and the largest eigenvalue $\lambda_{\max}(G)$, letting $$ M(G) := \max_{X,Y \subset V} \frac{e(X,Y)}{\sqrt{|X||Y|}} $$ (where $e(X,Y)$ denotes the number of edges between $X$ and $Y$), we have $$ M(G) \le \lambda_{\max}(G) \le \big(\frac14 \log|V| + 1 \big) \M(G). $$ Here the lower bound is attained if $G$ is regular or bi-regular, whereas the logarithmic factor in the upper bound, conjecturally, can be improved --- although we present an example showing that it cannot be replaced with a factor growing slower than $(\log |V|/\log\log|V|)^{1/8}$. Further refinements are established, particularly in the case where $G$ is bipartite.

Affiliated with

Also associated with

No associations

Rating

The Largest Eigenvalue and Bi-Average Degree of a Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Largest Eigenvalue and Bi-Average Degree of a Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Largest Eigenvalue and Bi-Average Degree of a Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7192