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}, 1le j_ile n_i.$ Then the composition $Q=T[H_1,dots , H_t]$ is a digraph with vertex set ${u_{i,j_i}mid 1le ile t, 1le j_ile n_i}$ and arc set $$A(Q)=cup^t_{i=1}A(H_i)cup {u_{ij_i}u_{pq_p}mid u_iu_pin A(T), 1le j_ile n_i, 1le q_ple n_p}.$$ When $T$ is arbitrary, we obtain the following result: every strong digraph composition $Q$ in which $n_ige 2$ for every $1leq ileq t$, has a good pair at every vertex of $Q.$ The condition of $n_ige 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.
تحميل البحث