2015/12/07 by Anna Lladó, Lladó, Anna, J.M. Aroca +2
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1512.02161
11 pages
arxiv created 2015/12/07 · openalex publication_date 2015/12/07 · arxiv updated 2015/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph G with n+1\choose 2 edges admits an edge decomposition G=H1⊕⋯ ⊕ Hn such that Hi has i edges and it is isomorphic to a subgraph of Hi+1, i=1,… ,n-1. We show that every bipartite graph G with n+1\choose 2 edges such that the degree sequence d1,… ,dk of one of the stable sets satisfies dk-i≥ n-i for each 0≤ i≤ 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.