Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have proposed very recently a question in the following link concerning the title of the current question: Difference of the maximum eigenvalue of a graph with the one of one-edge-deleted subgraph

I would like to ask my new related question as follows:

Is there a positive function $f(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges and any edge $e$ such that $G\setminus e$ is connected the inequality $\lambda(G)-\lambda(G\setminus e)\geq f(n,m)$ holds?

The notations are as in the above link. According to Prof. Chris Godsil's answer to my question posed in the above link one must have $f(n,m)\leq \frac{\pi^2}{(n+1)^2}$.

Edit: thanks to Anthony, I add the assumption $G\setminus e$ is connected.

share|improve this question
You need to assume that your graph is connected for your question to make sense. Given this, the answer is yes for trivial reasons. For each connected $G$, $G\setminus e$ has strictly smaller dominant eigenvalue, so there is a positive gap. Now since there are finitely many graphs with $n$ vertices and $m$ edges, when you take the minimum of these gaps, you get $f(m,n)>0$. Of course the more interesting question is to give a concrete lower bound. –  Anthony Quas Dec 18 '12 at 4:52
@Anthony. Thanks. As you see I add the further assumption. Actually I am asking for the best (greatest lower bound). –  Alireza Abdollahi Dec 18 '12 at 5:01
I think you only need to assume that $G$ is connected (not $G\setminus e$). –  Anthony Quas Dec 18 '12 at 5:25
Here's a guess for the minimum: Take a large clique and let each vertex of the clique be connected to the left end of a path (like a <a href="en.wikipedia.org/wiki/Lollipop"lollipop</a>!) Now if you remove the edge at the far end of the path, you make a very small difference to the dominant eigenvalue. You'd need to play around with the size of the path and the clique to see what gives the smallest difference. –  Anthony Quas Dec 18 '12 at 6:09
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer


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

Browse other questions tagged or ask your own question.