Degree sequences and graphs with disjoint spanning trees
2011
The design of an n 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=(d"1,d"2,...,d"n) is graphic if there is a simple graph G with degree sequence d. In this paper, it is proved that for a positive integer k, a graphic sequence d has a simple realization G which has k edge-disjoint spanning trees if and only if either both n=1 and d"1=0, or n>=2 and both d"n>=k and @?"i"="1^nd"i>=2k(n-1).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
5
Citations
NaN
KQI