Degree sequence realizations with given packing and covering of spanning trees
Designing networks in which every processor has a given number of connections often leads to graphic degree sequence realization models. A nonincreasing sequence d=(d1,d2,,dn) d = ( d 1 , d 2 ,  , d n ) is graphic if there is a simple graph G G with degree sequence d d . The spanning tree packing number of graph G G , denoted by ?(G) ? ( G ) , is the maximum number of edge-disjoint spanning trees in G G . The arboricity of graph G G , denoted by a(G) a ( G ) , is the minimum number of spanning trees whose union covers E(G) E ( G ) . In this paper, it is proved that, given a graphic sequence d=d1?d2???dn d = d 1 ? d 2 ? ? ? d n and integers k2?k1>0 k 2 ? k 1 > 0 , there exists a simple graph G G with degree sequence d d satisfying k1??(G)?a(G)?k2 k 1 ? ? ( G ) ? a ( G ) ? k 2 if and only if dn?k1 d n ? k 1 and 2 k 1 ( n ? 1 ) ? ? i = 1 n d i ? 2 k 2 ( n ? | I | ? 1 ) + 2 ? i ? I d i , where I = { i : d i  0 k > 0 , we obtain a characterization of graphic sequences with at least one realization G G satisfying a(G)?k a ( G ) ? k , and a characterization of graphic sequences with at least one realization G G satisfying ?(G)=a(G)=k ? ( G ) = a ( G ) = k .
graphic degree sequence spanning tree packing number arboricity