| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420221 | Discrete Applied Mathematics | 2011 | 6 Pages |
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.
