Designing networks in which every processor has a given number of connections often leads to graphic degree sequence realization models. A nonincreasing sequence d = (d(1), d(2), ... , d(n)) is graphic if there is a simple graph G with degree sequence d. The spanning tree packing number of graph G, denoted by tau (G), is the maximum number of edge-disjoint spanning trees in G. The arboricity of graph G, denoted by a(G), is the minimum number of spanning trees whose union covers E(G). In this paper, it is proved that, given a graphic sequence d = d(1) >= d(2) >= ... >= d(n) and integers k(2) >= k(1) > 0, there exists a simple graph G with degree sequence d satisfying k(1) <= tau(G) <= a(G) <= k(2) if and only if dn >= k(1) and 2k(1) (n - 1) <= Sigma(n)(i=1) d(i) <= 2k(2)(n - vertical bar I vertical bar - 1) + 2 Sigma(i is an element of) d(i), where I = {i : d(i) < k(2)}. As corollaries, for any integer k > 0, we obtain a characterization of graphic sequences with at least one realization G satisfying a(G) <= k, and a characterization of graphic sequences with at least one realization G satisfying tau(G) = a(G) = k. (c) 2014 Elsevier B.V. All rights reserved.
展开▼
