Degree sequences and graphs with disjoint spanning trees

The design of an nn processor network with a given number of connections from each processor and with a desirable strength of the network can be modeled as a degree sequence realization problem with certain desirable graphical properties. A nonincreasing sequence d=(d1,d2,…,dn)d=(d1,d2,…,dn) is graphic if there is a simple graph GG with degree sequence dd. In this paper, it is proved that for a positive integer kk, a graphic sequence dd has a simple realization GG which has kk edge-disjoint spanning trees if and only if either both n=1n=1 and d1=0d1=0, or n≥2n≥2 and both dn≥kdn≥k and ∑i=1ndi≥2k(n−1).

► Characterization of degree sequences with kk edge-disjoint spanning trees.
► Applications of strength and fractional arboricity.
► Application of nested decompositions based on subgraph densities.