Skip to main content
added 227 characters in body
Source Link
Shahrooz
  • 4.8k
  • 1
  • 24
  • 36

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.

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.

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.

Source Link
Shahrooz
  • 4.8k
  • 1
  • 24
  • 36

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.