1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Anthony Quas
    Commented Dec 18, 2012 at 4:52
  • $\begingroup$ @Anthony. Thanks. As you see I add the further assumption. Actually I am asking for the best (greatest lower bound). $\endgroup$
    – Alireza Abdollahi
    Commented Dec 18, 2012 at 5:01
  • $\begingroup$ I think you only need to assume that $G$ is connected (not $G\setminus e$). $\endgroup$
    – Anthony Quas
    Commented Dec 18, 2012 at 5:25
  • 2
    $\begingroup$ 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. $\endgroup$
    – Anthony Quas
    Commented Dec 18, 2012 at 6:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .