O's spectral conjecture for edge-connectivity of regular graphs

About 12 years old · traced to

Let GG be a dd-regular simple graph. For integers dd and tt, define

ρ(d,t)={d−4+(d+4)2−8t2,when t is odd,d−3+(d+3)2−8t2,when t is even.\rho(d,t)=\begin{cases} \frac{d-4 + \sqrt{(d+4)^2-8t}}{2}, & \text{when } t \text{ is odd}, \\ \frac{d-3 + \sqrt{(d+3)^2-8t}}{2}, & \text{when } t \text{ is even}.\end{cases}

O's conjecture. For t≥3t\geq 3, if

λ2(G)<ρ(d,t),\lambda_2(G)<\rho(d,t),

then κ′(G)≥t+1\kappa'(G)\geq t+1. This conjecture extends known spectral sufficient conditions for higher edge-connectivity of regular simple graphs; the supplied text does not state whether it has been proved or disproved.

References

Primary source

Suil O, “Edge-connectivity in regular multigraphs from eigenvalues”, arXiv:1409.6065 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.