TR-2017-08

Vertex-flames of countable digraphs preserving an Aharoni-Berger cut for each vertex

Attila Joó



Abstract

In the finite case an $r$-vertex-flame is a finite directed graph $F$ with $r\in V(F)$ in which for every vertex $v\neq r$ the indegree of $v$ is equal to $\kappa_F(r,v)$ (the local connectivity from $r$ to $v$ in $F$). G. Calvillo Vives proved that if $D$ is a finite directed graph with $r\in V(D)$, then there is a spanning subdigraph $F$ of $D$ such that $F$ is an $r$-vertex-flame and $\kappa_F(r,v)=\kappa_D(r,v)$ holds for every $v$. Our goal is to find the ``right'' infinite generalization of this theorem. We extend the definition of flame to the infinite case by demanding for every $v$ an internally disjoint system of $r\rightarrow v$ paths which uses all the ingoing edges of $v$. Instead of just preserving the local connectivities from $r$ as cardinals, we want to preserve in $F$ for every $v$ an Aharoni-Berger cut (see subsection 1.2) of $D$ from $r$ to $v$. The main result of this paper is to accomplish this for countable digraphs.


Bibtex entry:

@techreport{egres-17-08,
AUTHOR = {Jo{\'o}, Attila},
TITLE = {Vertex-flames of countable digraphs preserving an Aharoni-Berger cut for each vertex},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2017},
NUMBER = {TR-2017-08}
}


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