2019/06/19 by Gutin, Gregory, Sun, Yuefang
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1906.08052
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 u1,… , ut and let H1,… Ht be digraphs such that Hi has vertices ui,ji, 1≤ ji≤ ni. Then the composition Q=T[H1,… , Ht] is a digraph with vertex set \ui,ji| 1≤ i≤ t, 1≤ ji≤ ni\ and arc set A(Q)=∪ti=1A(Hi)∪ \uijiupqp| uiup∈ A(T), 1≤ ji≤ ni, 1≤ qp≤ np\. When T is arbitrary, we obtain the following result: every strong digraph composition Q in which ni≥ 2 for every 1≤ i≤ t, has a good pair at every vertex of Q. The condition of ni≥ 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.