The ascending subgraph decomposition problem
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
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.