Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs

Gregory Gutin; Yuefang Sun

paper

Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs

arXiv:1906.08052

Abstract

A digraph $D = (V, A)$ has a good pair at a vertex $r$ if $D$ has a pair of arc-disjoint in- and out-branchings rooted at $r$ . Let $T$ be a digraph with $t$ vertices $u_{1}, \dots, u_{t}$ and let $H_{1}, \dots H_{t}$ be digraphs such that $H_{i}$ has vertices $u_{i, j_{i}}, 1 \leq j_{i} \leq n_{i} .$ Then the composition $Q = T [H_{1}, \dots, H_{t}]$ is a digraph with vertex set ${u_{i, j_{i}} ∣ 1 \leq i \leq t, 1 \leq j_{i} \leq n_{i}}$ and arc set $A (Q) = \cup_{i = 1}^{t} A (H_{i}) \cup {u_{i j_{i}} u_{p q_{p}} ∣ u_{i} u_{p} \in A (T), 1 \leq j_{i} \leq n_{i}, 1 \leq q_{p} \leq n_{p}} .$ When $T$ is arbitrary, we obtain the following result: every strong digraph composition $Q$ in which $n_{i} \geq 2$ for every $1 \leq i \leq t$ , has a good pair at every vertex of $Q .$ The condition of $n_{i} \geq 2$ in this result cannot be relaxed. When $T$ is semicomplete, we characterize semicomplete compositions with a good pair, which generalizes the corresponding characterization by Bang-Jensen and Huang (J. Graph Theory, 1995) for quasi-transitive digraphs. As a result, we can decide in polynomial time whether a given semicomplete composition has a good pair rooted at a given vertex.