Bounds on the maximum eigenvalue of the adjacency matrix of a graph.

1.3k Views Asked by At

I managed to prove the following result for the maximum eigenvalue:

$$ d_\text{avg}\leq \lambda_{\max} \leq \Delta(G) $$

where $d_\text{avg}$ is the average degree of the graph while $\Delta(G)$ is the maximum degree.

Now I need to prove that:

$$ \frac 1 m \sum_{i\sim j} \sqrt{d_id_j} \leq \lambda_{\max} \leq \max_i \frac 1 {d_i} \sum_{i\sim j} \sqrt{d_id_j}. $$

Here $m$ is the number of edges and $d_i$ is the degree of node $i$. The sum runs for all the adjcent vertices of the graph. I was thinking about using some bounds on the Laplacian's eigenvalues but still I don't find a solution. Can someone help me?