A NOTE ON THE ASCENDING SUBGRAPH DECOMPOSITION PROBLEM

Let G be a graph with (n+12) edges. We say G has an ascending subgraph decomposition (ASD) if the edge set of G can be partitioned into n sets generating graphs G1, G2,...,Gn such that |E(Gi)| = i (for i = 1, 2,..., n) and Gi is isomorphic to a subgraph of Gi+1 for i = 1, 2,..., n - 1. In this note, we prove that if G is a graph of maximum degree d ≤ ⌊(n + 1)/2⌋ on (n+12) edges, then G has an ASD. Moreover, we show that if d ≤ ⌊(n-1)/2⌋, then G has an ASD with each member a matching. Subsequently, we also verify that every regular graph of degree a prime power has an ASD. © 1990.