A (d, k) -forest is a forest consisting of trees whose diameters are at most d and whose maximum vertex degree,Δ is at most k. The (d, k)-arboricity of a graph G is the minimum number of (d, k)-forests needed to cover E(G). This concept is a common generalization of linear k-arboricity and star arboricity. Using a probabilistic approach developed recently for linear karboricity, we obtain an upper bound on the (d, k)-arboricity of r-regular graphs.
|Number of pages||8|
|Journal||Australasian Journal of Combinatorics|
|Publication status||Published - 2000|