The Ascending Star Subgraph Decomposition of Some Star Forests

Huaitang Chen1, Kejie Ma2, Huishan Zhou3
1Mathematics Department. Linyi Teachers’ College Linyi, Shandong P.R. of China
2Institute of Operations Reseasrch Qufu Normal University Qufu, Shandong P.R. of China
3 Department of Mathematics and Computer Sciences Georgia State University University Plaza Atlanta, Georgia, 30303

Abstract

Let \(G\) be a graph of size \(\binom{n+1}{2}\) for some integer \(n \geq 2\). Then \(G\) is said to have an ascending star subgraph decomposition if \(G\) can be decomposed into \(n\) subgraphs \(G_1, G_2, \ldots, G_n\) such that each \(G_i\) is a star of size \(i\) with \(1 \leq i \leq n\). We shall prove in this paper that a star forest with size \(\binom{n+1}{2}\) possesses an ascending star subgraph decomposition under some conditions on the number of components or the size of components.