Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 219-226 |
Number of pages | 8 |
Journal | Australasian Journal of Combinatorics |
Volume | 22 |
Publication status | Published - 2000 |
Externally published | Yes |