Edge-connectivity in regular multigraphs from eigenvalues
Suil O
所有作者
Suil O
文献摘要
Let G be a d-regular multigraph, and let λ2(G) be the second
largest eigenvalue of G. In this paper, we prove that if $\lambda_2(G) <
\frac{d-1+\sqrt{9d^2-10d+17}}4,thenGis2−edge−connected.Furthermore,fort\ge2weshowthatGis(t+1)−edge−connectedwhen\lambda_2(G)<d-t$, and
in fact when λ2(G)<d−t+1 if t is odd.