A note on the ascending subgraph decomposition problem

Hung-Lin Fu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)315-318
Number of pages4
JournalDiscrete Mathematics
Volume84
Issue number3
DOIs
StatePublished - 15 Oct 1990

Fingerprint Dive into the research topics of 'A note on the ascending subgraph decomposition problem'. Together they form a unique fingerprint.

Cite this