Cioabă and Wong's spectral spanning-tree packing conjecture

About 5 years old · traced to

Let m≥1m\geq 1 be an integer, and let GG be a dd-regular graph with d≥2m+2d\geq 2m+2. Let λ2(G)\lambda_2(G) be the second-largest adjacency eigenvalue of GG, and let σ(G)\sigma(G) denote the maximum number of edge-disjoint spanning trees in GG. Cioabă and Wong's conjecture. If

λ2(G)<d−2m+1d+1,\lambda_2(G)<d-\frac{2m+1}{d+1},

then

σ(G)≥m+1.\sigma(G)\geq m+1.

This conjecture gives a factor-of-two improvement over the earlier spectral condition implying the existence of m+1m+1 edge-disjoint spanning trees; it was verified for m∈{1,2}m\in\{1,2\}, while the paper constructs examples showing that the conjectured bound is essentially best possible.

References

Primary source

Sebastian M. Cioabă, Anthony Ostuni, Davin Park, Sriya Potluri, Tanay Wakhare and Wiseley Wong, “Extremal Graphs for a Spectral Inequality on Edge-Disjoint Spanning Trees”, arXiv:2104.01665 (2021).

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.