Star decomposition of graphs
Yang Zhao, Baoyindureng Wu · Discrete Mathematics Algorithms and Applications · 2015
Let k be a positive integer and G be a graph. If d(u) + d(v) ≥ 4k - 3 for any uv ∈ E(G), then G admits a star decomposition in which all stars have size at least k. In particular, every graph G with δ(G) ≥ 2k - 1 admits such a decomposition. The bounds are best possible, in the sense that there exist infinitely many graphs G with δ(G) ≥ 2k - 2 and without such a decomposition.