2026-04-18T04:05:50Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/1123252025-07-17T10:24:38Zcom_2072_1033col_2072_452950

On star forest ascending subgraph decomposition Aroca Farrerons, José María Lladó Sánchez, Ana M. Universitat Politècnica de Catalunya. Departament de Matemàtiques Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria Graph theory Ascending graph decomposition Grafs, Teoria de Classificació AMS::05 Combinatorics::05C Graph theory The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph G with (n+12) 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+12) edges such that the degree sequence d1,…,dk of one of the stable sets satisfies dk-i=n-ifor each0=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. Peer Reviewed Postprint (author's final draft) 2017-02-03 Article Aroca, J., Llado, A. On star forest ascending subgraph decomposition. "Electronic journal of combinatorics", 3 Febrer 2017, vol. 24, núm. 1, p. 1-12. 1077-8926 https://hdl.handle.net/2117/112325 eng http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p14 http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access Attribution-NonCommercial-NoDerivs 3.0 Spain 12 p. application/pdf