TY - JOUR
T1 - A note on the ascending subgraph decomposition problem
AU - Fu, Hung-Lin
PY - 1990/10/15
Y1 - 1990/10/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0011286134&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(90)90137-7
DO - 10.1016/0012-365X(90)90137-7
M3 - Article
AN - SCOPUS:0011286134
VL - 84
SP - 315
EP - 318
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 3
ER -