Some results on ascending subgraph decomposition

Abstract

Let G be a graph of positive size q, and let n be that positive integer for which (ⁿ⁺¹₂) ≤ q < (ⁿ⁺²₂). Then G is said to have an ascending subgraph decomposition if G can be decomposed into n subgraphs G₁ , G₂, ⋯ , G_n without isolated vertices such that G_i is isomorphic to a proper subgraph of G_i+1, for i = 1, 2, ⋯ , n -1. The graph G is shown to have an ascending subgraph decomposition when either G = K_n - H_n+[(n,-1)/2] (where H_n+[(n-1)/2] is a subgraph of K_n with at most n + [(n-1)/2] edges) or G is any complete bipartite graph.