On star forest ascending subgraph decomposition (Q510324): Difference between revisions
From MaRDI portal
Latest revision as of 11:25, 13 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On star forest ascending subgraph decomposition |
scientific article |
Statements
On star forest ascending subgraph decomposition (English)
0 references
17 February 2017
0 references
Summary: 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}\geq n-i\; \text{for each}\; 0\leq i\leq 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.
0 references
ascending graph decomposition
0 references