The spectral-radius conjecture for extremal graphs with edge-disjoint spanning trees

Less than 1 year old · traced to

Let kk and cc be integers with 0≤c≤k−10\le c\le k-1. For 0≤c≤k−20\le c\le k-2, let H1(n,k,c)\mathcal{H}_1(n,k,c) be the class of all (k+c)(k+c)-edge-connected graphs HH of order nn for which there is a partition V(H)=U∪TV(H)=U\cup T such that ∣U∣=n−2c−2|U|=n-2c-2, ∣T∣=2c+2|T|=2c+2, H[U]≅Kn−2c−2H[U]\cong K_{n-2c-2}, 2c2+2c+1≤eH(T)≤2c2+3c+12c^2+2c+1\le e_H(T)\le 2c^2+3c+1, and eH(T,U)=k(2c+2)−1−eH(T)e_H(T,U)=k(2c+2)-1-e_H(T). Let H1∗(n,k,c)H_1^*(n,k,c) maximize the spectral radius in H1(n,k,c)\mathcal{H}_1(n,k,c). For c=k−1c=k-1, let H2(n,k,c)\mathcal{H}_2(n,k,c) be the class of all (k+c)(k+c)-edge-connected graphs HH of order nn for which there is a partition V(H)=U∪TV(H)=U\cup T such that ∣U∣=n−2c−3|U|=n-2c-3, ∣T∣=2c+3|T|=2c+3, H[U]≅Kn−2c−3H[U]\cong K_{n-2c-3}, eH(T)=2c2+3c+1e_H(T)=2c^2+3c+1, and eH(T,U)=2c+1e_H(T,U)=2c+1. Let H2∗(n,k,c)H_2^*(n,k,c) maximize the spectral radius in H2(n,k,c)\mathcal{H}_2(n,k,c). Spectral-radius extremal conjecture. Let nn be sufficiently large. If 0≤c≤k−20\le c\le k-2 and GG is a (k+c)(k+c)-edge-connected graph of order nn with ρ(G)≥ρ(H1∗(n,k,c))\rho(G)\ge\rho(H_1^*(n,k,c)), then τ(G)≥k\tau(G)\ge k unless GG is a graph in H1(n,k,c)\mathcal{H}_1(n,k,c) with maximum spectral radius. If c=k−1c=k-1 and ρ(G)≥ρ(H2∗(n,k,c))\rho(G)\ge\rho(H_2^*(n,k,c)), then τ(G)≥k\tau(G)\ge k unless GG is a graph in H2(n,k,c)\mathcal{H}_2(n,k,c) with maximum spectral radius. The conjecture proposes sharp spectral-radius thresholds guaranteeing kk edge-disjoint spanning trees, with the displayed candidate classes as the exceptional extremal graphs. The discussion is explicitly heuristic and does not prove the assertion; the cases c=0c=0 and (k,c)=(2,1)(k,c)=(2,1) agree with the paper's previously established extremal results, while the general cases remain open.

References

Primary source

Yongbin Gao and Ligong Wang, “Spectral radius conditions for edge-disjoint spanning trees in (k+c)-edge-connected graphs”, arXiv:2604.21470 (2026).

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.