In-arborescence

Definition

In-arborescence

Let $D=(V,A)$ be a finite directed graph and $r\in V$. An in-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}v⇝r\text{for every }v\in V.$$

Here ${\mathrm{deg}}_T^{+}(v)$ counts the edges leaving $v$ in $T$, and $v⇝r$ means that a directed path from $v$ to $r$ exists. Each non-root vertex has one outgoing edge, so its path to $r$ is unique. Equivalently, the underlying undirected graph of $T$ is a tree with all edges directed towards $r$.

The highlighted edges form the unique directed path from $c$ to $r$. Reversing every edge gives an out-arborescence.