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=(d1,d2,…,dn) is graphic if there is a simple graph GG with degree sequence dd. The spanning tree packing number of graph GG, denoted by τ(G)τ(G), is the maximum number of edge-disjoint spanning trees in GG. The arboricity of graph GG, 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≥⋯≥dnd=d1≥d2≥⋯≥dn and integers k2≥k1>0k2≥k1>0, there exists a simple graph GG with degree sequence dd satisfying k1≤τ(G)≤a(G)≤k2k1≤τ(G)≤a(G)≤k2 if and only if dn≥k1dn≥k1 and 2k1(n−1)≤∑i=1ndi≤2k2(n−|I|−1)+2∑i∈Idi, where I={i:di0k>0, we obtain a characterization of graphic sequences with at least one realization GG satisfying a(G)≤ka(G)≤k, and a characterization of graphic sequences with at least one realization GG satisfying τ(G)=a(G)=kτ(G)=a(G)=k.