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

From papers

Let kk and cc be integers with 0ck10\le c\le k-1. For 0ck20\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)=UTV(H)=U\cup T such that U=n2c2|U|=n-2c-2, T=2c+2|T|=2c+2, H[U]Kn2c2H[U]\cong K_{n-2c-2}, 2c2+2c+1eH(T)2c2+3c+12c^2+2c+1\le e_H(T)\le 2c^2+3c+1, and eH(T,U)=k(2c+2)1eH(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=k1c=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)=UTV(H)=U\cup T such that U=n2c3|U|=n-2c-3, T=2c+3|T|=2c+3, H[U]Kn2c3H[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 0ck20\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=k1c=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.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.