TY - JOUR

T1 - On ascending subgraph decomposition of graphs

AU - Liang, Zhihe

AU - Fu, Hung-Lin

PY - 2017/7/4

Y1 - 2017/7/4

N2 - Let G be a graph of positive size q, and let n be that positive integer for which (Figure presented.). It was conjectured by Alavi et al that the G can be decomposed into subgraphs G1, G2, …,Gn such that Gi is isomorphic to a proper subgraph of Gi+1 for 1 ≤ i ≤ n−1. Since the conjecture was posed around 25 years many special classes of graphs have been verified to have ascending subgraph decomposition defined above. Because of the interesting nature of the structure of graphs, many researchers have devoted themselves to work on this problem and also provided several extended versions of such decompositions. Mainly, the size of G and the structure of Gi’s are concerned. As hard as we work on this problem, we find the fascinating inside of this seemingly easy conjecture. This is the reason, we decide to make a survey of this decomposition and hopefully, we would (be very happy to) see the ASD conjecture proved to be true in the near future by some talented researchers.

AB - Let G be a graph of positive size q, and let n be that positive integer for which (Figure presented.). It was conjectured by Alavi et al that the G can be decomposed into subgraphs G1, G2, …,Gn such that Gi is isomorphic to a proper subgraph of Gi+1 for 1 ≤ i ≤ n−1. Since the conjecture was posed around 25 years many special classes of graphs have been verified to have ascending subgraph decomposition defined above. Because of the interesting nature of the structure of graphs, many researchers have devoted themselves to work on this problem and also provided several extended versions of such decompositions. Mainly, the size of G and the structure of Gi’s are concerned. As hard as we work on this problem, we find the fascinating inside of this seemingly easy conjecture. This is the reason, we decide to make a survey of this decomposition and hopefully, we would (be very happy to) see the ASD conjecture proved to be true in the near future by some talented researchers.

KW - ascending subgraph decomposition of graph

KW - matching

KW - path

KW - star

KW - subset partition

UR - http://www.scopus.com/inward/record.url?scp=85035056853&partnerID=8YFLogxK

U2 - 10.1080/09720529.2015.1032619

DO - 10.1080/09720529.2015.1032619

M3 - Article

AN - SCOPUS:85035056853

VL - 20

SP - 1135

EP - 1149

JO - Journal of Discrete Mathematical Sciences and Cryptography

JF - Journal of Discrete Mathematical Sciences and Cryptography

SN - 0972-0529

IS - 5

ER -