Out-arborescence

Definition

Out-arborescenc

Let $D=(V,A)$ be a finite directed graph and $r\in V$. An out-arborescence rooted at $r$ is a spanning subgraph $T=(V,A^{\prime })$, where $A^{\prime }\subseteq A$, such that

$${\mathrm{deg}}_T^{-}(r)=0,{\mathrm{deg}}_T^{-}(v)=1\text{for every }v\in V\setminus \{r\},\text{and}r⇝v\text{for every }v\in V.$$

Here ${\mathrm{deg}}_T^{-}(v)$ counts the edges entering $v$ in $T$, and $r⇝v$ means that a directed path from $r$ to $v$ exists. The indegree condition then makes this path unique: every vertex except $r$ has exactly one parent. Equivalently, the underlying undirected graph of $T$ is a tree with all edges directed away from $r$.

On the left, the highlighted edges form the unique path from $r$ to $c$. In the middle, reversing one edge leaves $a$ with indegree zero and $r$ with indegree one. On the right, $c$ has indegree two: both $r\to a\to c$ and $r\to b\to c$ reach it. Neither of the latter two graphs is an arborescence.