On the ascending star subgraphs decomposition of star forests (Q1340139): Difference between revisions

Let \(G\) be a graph of size \(\left(\begin{smallmatrix} n+1\\ 2\end{smallmatrix}\right)\) for some integer \(n\geq 2\). Then \(G\) is said to have an ascending star subgraph decomposition if the edge set of \(G\) can be decomposed into \(n\) subgraphs \(G_ 1,G_ 2,\dots, G_ n\) such that each \(G_ i\) is a star of size \(i\) for \(1\leq i\leq n\). The authors show that a star forest of size \(\left(\begin{smallmatrix} n+1\\ 2\end{smallmatrix}\right)\) possesses an ascending star decomposition if the size of each component is at least \(n\). Their procedure is constructive in the sense that they provide an algorithm that gives the desired construction and then verify its correctness.