Skip to main content
Took away typo correction that was fixed
Source Link
Cam McLeman
  • 8.5k
  • 3
  • 51
  • 65

If your graph is bipartite (a natural restriction if the motivation comes from Hueckel theory), then the symmetry of the spectrum tells you a pretty good deal. If 0 is an eigenvalue of your graph, then it is a double eigenvalue, and so $\lambda_{n+1}-\lambda_n=0-0=0$. If 0 is not an eigenvalue of your graph, then $\lambda_n$ is the least positive eigenvalue of your graph, and $\lambda_{n+1}$ is its negative. So studying $\lambda_n$ in this case is in fact equivalent to studying the difference $\lambda_n-\lambda_{n+1}=2\lambda_n$. (Incidentally, isn't your $R(G)$ always $\lambda_n$ since $\lambda_n\geq \lambda_{n+1}$? Did you want absolute values?).

If you can also assume some other assumptions on your graph (e.g., that it has a unique perfect matching...again, fairly reasonable from Hueckel theory), then more can be said. Look up works by Godsil, in particular his paper "Inverses of Trees." For example (roughly), since zero is not an eigenvalue of your graph, roughly stemming from the invertibility of the adjacency matrix is the bound $\lambda_m\leq \frac{1}{\lambda_1}$, with equality under a certain technical condition on your graph (a "self-dual"ish type property). For a lower bound, Godsil shows that $\lambda_n$ of any such graph is bounded below by $\lambda_n$ of an explicit graph constructed in the paper (it is a corona product of graphs, though he doesn't use this terminology. In fact, I think it's specifically the corona $P_n\circ K_1$ which gives the lowest possible $\lambda_n$ among such graphs).

Hope that helps.

If your graph is bipartite (a natural restriction if the motivation comes from Hueckel theory), then the symmetry of the spectrum tells you a pretty good deal. If 0 is an eigenvalue of your graph, then it is a double eigenvalue, and so $\lambda_{n+1}-\lambda_n=0-0=0$. If 0 is not an eigenvalue of your graph, then $\lambda_n$ is the least positive eigenvalue of your graph, and $\lambda_{n+1}$ is its negative. So studying $\lambda_n$ in this case is in fact equivalent to studying the difference $\lambda_n-\lambda_{n+1}=2\lambda_n$. (Incidentally, isn't your $R(G)$ always $\lambda_n$ since $\lambda_n\geq \lambda_{n+1}$? Did you want absolute values?).

If you can also assume some other assumptions on your graph (e.g., that it has a unique perfect matching...again, fairly reasonable from Hueckel theory), then more can be said. Look up works by Godsil, in particular his paper "Inverses of Trees." For example (roughly), since zero is not an eigenvalue of your graph, roughly stemming from the invertibility of the adjacency matrix is the bound $\lambda_m\leq \frac{1}{\lambda_1}$, with equality under a certain technical condition on your graph (a "self-dual"ish type property). For a lower bound, Godsil shows that $\lambda_n$ of any such graph is bounded below by $\lambda_n$ of an explicit graph constructed in the paper (it is a corona product of graphs, though he doesn't use this terminology. In fact, I think it's specifically the corona $P_n\circ K_1$ which gives the lowest possible $\lambda_n$ among such graphs).

Hope that helps.

If your graph is bipartite (a natural restriction if the motivation comes from Hueckel theory), then the symmetry of the spectrum tells you a pretty good deal. If 0 is an eigenvalue of your graph, then it is a double eigenvalue, and so $\lambda_{n+1}-\lambda_n=0-0=0$. If 0 is not an eigenvalue of your graph, then $\lambda_n$ is the least positive eigenvalue of your graph, and $\lambda_{n+1}$ is its negative. So studying $\lambda_n$ in this case is in fact equivalent to studying the difference $\lambda_n-\lambda_{n+1}=2\lambda_n$.

If you can also assume some other assumptions on your graph (e.g., that it has a unique perfect matching...again, fairly reasonable from Hueckel theory), then more can be said. Look up works by Godsil, in particular his paper "Inverses of Trees." For example (roughly), since zero is not an eigenvalue of your graph, roughly stemming from the invertibility of the adjacency matrix is the bound $\lambda_m\leq \frac{1}{\lambda_1}$, with equality under a certain technical condition on your graph (a "self-dual"ish type property). For a lower bound, Godsil shows that $\lambda_n$ of any such graph is bounded below by $\lambda_n$ of an explicit graph constructed in the paper (it is a corona product of graphs, though he doesn't use this terminology. In fact, I think it's specifically the corona $P_n\circ K_1$ which gives the lowest possible $\lambda_n$ among such graphs).

Hope that helps.

Source Link
Cam McLeman
  • 8.5k
  • 3
  • 51
  • 65

If your graph is bipartite (a natural restriction if the motivation comes from Hueckel theory), then the symmetry of the spectrum tells you a pretty good deal. If 0 is an eigenvalue of your graph, then it is a double eigenvalue, and so $\lambda_{n+1}-\lambda_n=0-0=0$. If 0 is not an eigenvalue of your graph, then $\lambda_n$ is the least positive eigenvalue of your graph, and $\lambda_{n+1}$ is its negative. So studying $\lambda_n$ in this case is in fact equivalent to studying the difference $\lambda_n-\lambda_{n+1}=2\lambda_n$. (Incidentally, isn't your $R(G)$ always $\lambda_n$ since $\lambda_n\geq \lambda_{n+1}$? Did you want absolute values?).

If you can also assume some other assumptions on your graph (e.g., that it has a unique perfect matching...again, fairly reasonable from Hueckel theory), then more can be said. Look up works by Godsil, in particular his paper "Inverses of Trees." For example (roughly), since zero is not an eigenvalue of your graph, roughly stemming from the invertibility of the adjacency matrix is the bound $\lambda_m\leq \frac{1}{\lambda_1}$, with equality under a certain technical condition on your graph (a "self-dual"ish type property). For a lower bound, Godsil shows that $\lambda_n$ of any such graph is bounded below by $\lambda_n$ of an explicit graph constructed in the paper (it is a corona product of graphs, though he doesn't use this terminology. In fact, I think it's specifically the corona $P_n\circ K_1$ which gives the lowest possible $\lambda_n$ among such graphs).

Hope that helps.