# Problem (proposed by Alavi, Boals, Chartrand, Erdös and Oellermann) [1]

Suppose $$G$$ is a graph with $$n (n+1)/2$$ edges (for some $$n$$ which is not necessarily the number of vertices). Prove that $$G$$ can be edge-partitioned into subgraphs $$G_i$$ with $$i$$ edges such that $$G_i$$ is isomorphic to a subgraph of $$G_{i+1}$$ for $$i=1, \dots, n-1$$.

A special case is the decomposition of star forests into stars (which is the so-called suitcase problem [1] of partitioning the set $$\{ 1, \dots, n \}$$ into $$k$$ parts with given sums $$a_1, \dots, a_k$$ for any $$a_i \leq n$$ and $$\sum a_i = n(n+1)/2$$). The suitcase problem was solved by Ma, Zhou and Zhou [2] [3].

A more general case was provided by Huaitand and Kejie where they proved that regular graphs has an ascending subgraph decomposition provided the density is less than $$2/3$$. They also proved that every regular bipartite graph as an ascending subgraph decomposition. [5]

The regular case was covered later by Fu and Hu [6] where they show that every regular graph, $$G$$ with $$\vert E(G)\vert=$$ $${n \choose 2} + t$$ has an ascending subgraph decomposition with $$G_i$$ having $$\vert E(G_i)\vert=i$$ for $$i=1,\ldots n-1$$ and $$\vert E(G_n)\vert=n+t$$

In [7] Chen, Fu, Wang, and Zhou extend the concept of ascending subgraph decomposition to integers and apply graph theoretical results to determine when the set [n]={1,2,...n} can be partitioned into sets with prescribed sums.

In 2006, Krishnan and Nagarajan [4] generalized this problem by seeking a $$(a,d)$$-ascending subgraph decomposition. Whereby the first subgraph has $$a$$ edges, and number of edges of each subsequent subgraph is $$d$$ more than the previous. They provide a characterization of $$(a,d)$$-ascending subgraph decomposition for wheels.

Even with all of this progress and applications, the problem remains open, especially for non-regular graphs.

Bibliography
1 Y. Alavi, A. J. Boals, G. Chartrand, P. Erdös and O. R. Oellermann, The ascending subgraph decomposition problem, Congressus Numerantium 58 (1987), 7-14.

2 K. J. Ma, H. S. Zhou and J. Q. Zhou, On the ascending star subgraph decomposition of star forests, Combinatorica 14 (1994), 307-320.

3 K. J. Ma, H. S. Zhou and J. Q. Zhou, A proof of the Alavi conjecture on integer decomposition, (Chinese), Acta Math. Sinica 38 (1995), 635-641. (Link in Chinese)

4 A, Nagarajan and S. Navaneetha Krishnan, The (a, d)-Ascending Subgraph Decomposition, Tamkand Journal of Mathematics, 37 (2006), 377-390.

5 C. Huaitang and M. Kejie, On the ascending subgraph decompositions of regular graphs, Appl. Math. - A J. of Chinese Universities 13 (1998). 165-170

6 H.L. Fu and W. Hu, Acsending Subgraph Decompositions of Regular Graphs, Discrete Mathematics 253 (2002). 11-18.

7 F.L. Chen, H.L. Fu, Y. Wang and J. Zhou, Partition of a Set of Integers into Sets with Prescribed Sums, Taiwanese J. of Math. 9 (2005), 628-638.