The ascending subgraph decomposition problem

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.

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.