TR-2015-11

Packing countably many branchings with prescribed root-sets in digraphs without backward-infinite paths

Attila Joó



Abstract

We generalize an unpublished result of C. Thomassen. Let $ D=(V,A) $ be a digraph without backward-infinite paths and let $ \{ V_i \}_{i\in \mathbb{N}} $ be a multiset of subsets of $ V $. We show that if all $ v\in V $ is simultaneously reachable from the sets $ V_i $ by edge-disjoint paths, then there exists a system of edge-disjoint spanning branchings $ \{ \mathcal{B}_i \}_{i\in \mathbb{N}} $ in $ D $ where the root-set of $ \mathcal{B}_i $ is $ V_i $.


Bibtex entry:

@techreport{egres-15-11,
AUTHOR = {Jo{\'o}, Attila},
TITLE = {Packing countably many branchings with prescribed root-sets in digraphs without backward-infinite paths},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-11}
}


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