Let $G$ be a graph and $e$ be an edge of the graph $G$ such that the subgraph $G\setminus e$ is connected. The subgraph $G\setminus e$ is the subgraph of $G$ obtained by deletion of the edge $e$ of $G$. Assume that $G$ has $n$ vertices. Is it true that $\lambda(G)-\lambda(G\setminus e)\geq \frac{1}{n}$? Here $\lambda(G)$ denotes the maximum eigenvalue of adjacency matrix of $G$.
$\begingroup$
$\endgroup$
asked Dec 17, 2012 at 19:19
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
It's always useful to test these questions on actual examples. The largest eigenvalue of the cycle $C_n$ is 2 and the largest eigenvalue of the path $P_n$ on $n$ vertices is $2\cos(\pi/(n+1))$. When $n=8$, this is 1.879385 and $2-1.8793852=0.120615 <1/8$.
In fact it is not hard to see that for large $n$ the difference $2-2\cos(\pi/(n+1))$ is of order $\pi^2/(n+1)^2$, and so your lower bound is not even of the right order.
answered Dec 17, 2012 at 21:44
$\begingroup$
$\endgroup$
0
This conjecture is not true in general. For example, let $G$ be a graph that obtained from joining the end vertex of $P_3$, $P_3$ and $P_4$, where it is an star-like tree. This graph has largest eigenvalue equal to $2.02852$. Now join the end vertex of $P_4$ to the end vertex of $P_3$. Therefore we added an edge to the previous graph. The largest eigenvalue of this graph is $2.13578$. Then the difference of this values is $0.10726$. But this graph has $8$ vertices and $1/8=0.125$. It is a counter example.
Also, we can construct a family of star-like tree that does not have this property. Also, I think for any polynomial $f(n)$, we can construct a graph $G$ such that $\lambda(G)-\lambda(G-e)\geq \frac{1}{f(n)}$ is not true.
