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

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$.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
@Chris. Many Thanks. –  Alireza Abdollahi Dec 18 '12 at 4:04

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.

share|improve this answer
    
@Shahrooz. Many thanks. –  Alireza Abdollahi Dec 18 '12 at 4:04

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.