On star-forest ascending subgraph decomposition
Authors:
- Anna LladóALAnna Lladó
- Josep Maria ArocaJAJosep Maria Aroca
Preprint
Abstract
The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph $G$ with ${n+1\choose 2}$ edges admits an edge decomposition $G=H_1\oplus\cdots \oplus H_n$ such that $H_i$ has $i$ edges and it is isomorphic to a subgraph of $H_{i+1}$, $i=1,\ldots ,n-1$. We show that every bipartite graph $G$ with ${n+1\choose 2}$ edges such that the degree sequence $d_1,\ldots ,d_k$ of one of the stable sets satisfies $ d_{k-i}\ge n-i\; \text{for each}\; 0\le i\le k-1,$, admits an ascending subgraph decomposition with star forests. We also give a necessary condition on the degree sequence which is not far from the above sufficient one.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On the modular sumset partition problemEuropean Journal of Combinatorics, 2012
- PARTITION OF A SET OF INTEGERS INTO SUBSETS WITH PRESCRIBED SUMSTaiwanese Journal of Mathematics, 2005
- Edge Disjoint Paths of Increasing Order in Complete Bipartite GraphsElectronic Notes in Discrete Mathematics, 2005
- Ascending subgraph decompositions of regular graphsDiscrete Mathematics, 2002
- A note on ascending subgraph decompositions of complete multipartite graphsDiscrete Mathematics, 2001
- On the ascending subgraph decompositions of regular graphsApplied Mathematics-A Journal of Chinese Universities, 1998
- Restricted Edge-colourings of Bipartite GraphsCombinatorics, Probability and Computing, 1996
- On the ascending star subgraph decomposition of star forestsCombinatorica, 1994
- A note on the ascending subgraph decomposition problemDiscrete Mathematics, 1990