Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

where $d_{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?

share|improve this question
    
I think I solved the problem just selecting accurately the vector in the Rayleigh ratio and using the Courant-Fisher theorem for the upper bound. I don't have a lot of time to wrote it here but if someone needs the proof we can discuss about it. –  user73793 Apr 23 '13 at 9:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.