1
$\begingroup$

Let $D=(V,A)$ be a directed graph with root $r$. An $r$-arborescence of $D$ is a subgraph such that for any $v\in V-r$, there is exactly one directed path from $r$ to $v$. Hence an $r$-arborescence is a directed spanning tree whose arcs are directed away from $r$.

Question: Is there a directed graph $D=(V,A)$ with root $r$ such that any two $r$-arborescences of $D$ are arc-disjoint?

$\endgroup$
1
$\begingroup$

Leaving aside the trivial case (graphs which only have one $r$-arborescence), this won't be possible.

Suppose $(V,E)$ is an $r$-arborescence of $(V,A)$. Then $E$ contains some (nonzero) number of arcs $(r,s_1),\ldots,(r,s_k)$ out of the root (otherwise we are in a trivial case). Now if $(V,F)$ is another arborescence, then either

  • $F$ also contains some $(r,s_i)$, so the arborescences are not arc-disjoint, or
  • $F$ contains $(r,t)$ for some $t\notin\{s_1,\ldots,s_k\}$, and for each $i$, an arc $(p_i,s_i)$ for some (not necessarily distinct) vertices $p_1,\ldots,p_k\neq r$. But then we can replace one such arc with $(r,s_i)$ - it is easy to see that $(V,F\cup\{(r,s_i)\}\setminus\{(p_i,s_i)\})$ is again an $r$-arborescence: For any vertex $v$ in the subtree of $(V,F)$ rooted at $s_i$, the only path from $r$ to $v$ is now the old one, with the prefix up to $s_i$ replaced by $(r,s_i)$; for all other vertices, the paths remain unchanged. This new arborescence is distinct from $(V,E)$ since it still contains $(r,t)$, but they are not arc-disjoint since they both contain $(r,s_i)$.
$\endgroup$
  • $\begingroup$ Thank you so much for such a quick reply! $\endgroup$ – Han Xiao Aug 9 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.