Loading...
Loading...

Go to the content (press return)

On the ascending subgraph decomposition problem for bipartite graphs

Author
Aroca, J.; Llado, A.; Slamin, S.
Type of activity
Journal article
Journal
Electronic notes in discrete mathematics
Date of publication
2014-09
Volume
46
First page
19
Last page
26
DOI
https://doi.org/10.1016/j.endm.2014.08.004 Open in new window
Project funding
2009SGR1387
Optimización y problemas extremales en teoria de grafos y combinatoria. Aplicacions a les redes de comunicación
Repository
http://hdl.handle.net/2117/26088 Open in new window
URL
http://www.sciencedirect.com/science/article/pii/S1571065314000055 Open in new window
Abstract
The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph G with View the MathML source(n+12) edges admits an edge decomposition G=H1¿¿¿HnG=H1¿¿¿Hn such that HiHi has i edges and is isomorphic to a subgraph of Hi+1Hi+1, i=1,…,n-1i=1,…,n-1. We show that every bipartite graph G with View the MathML source(n+12) edges such that the degree sequence d1,…,dkd1,…,dk of one of the stable sets satisfies di=n-i+2di=n-i+2, 1=i
Citation
Aroca, J.; Llado, A.; Slamin, S. On the ascending subgraph decomposition problem for bipartite graphs. "Electronic notes in discrete mathematics", Setembre 2014, vol. 46, p. 19-26.
Keywords
Ascending subgraph decomposition, Sumset partition problem
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Attachments