Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs
share
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,... , u_t and let H_1,... H_t be digraphs such that H_i has vertices u_i,j_i, 1< j_i< n_i. Then the composition Q=T[H_1,... , H_t] is a digraph with vertex set {u_i,j_i| 1< i< t, 1< j_i< n_i} and arc set A(Q)=∪^t_i=1A(H_i)∪{u_ij_iu_pq_p| u_iu_p∈ A(T), 1< j_i< n_i, 1< q_p< n_p}. When T is arbitrary, we obtain the following result: every strong digraph composition Q in which n_i> 2 for every 1≤ i≤ t, has a good pair at every vertex of Q. The condition of n_i> 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.
READ FULL TEXT