TR-2014-13

Edmonds' Branching Theorem in Digraphs without Forward-infinite Paths

Attila Joó



Abstract

By a well-known theorem of Edmonds if a finite digraph is $k$-edge-connected from vertex $r$ then it has $k$ edge-disjoint spanning arborescences rooted at $r$. As it was shown by R. Aharoni and C. Thomassen, this does not remain true for infinite digraphs. Thomassen also proved that for the class of digraphs without backward-infinite paths the above theorem of Edmonds remains true. Our main result is that for digraphs without forward-infinite paths the theorem is also true, even in general form.


Bibtex entry:

@techreport{egres-14-13,
AUTHOR = {Jo{\'o}, Attila},
TITLE = {Edmonds' Branching Theorem in Digraphs without Forward-infinite Paths},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2014},
NUMBER = {TR-2014-13}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!