Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs
share
A digraph D=(V,A) has a good decomposition if A has two disjoint sets A_1 and A_2 such that both (V,A_1) and (V,A_2) are strong. 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}. For digraph compositions Q=T[H_1,... H_t], we obtain sufficient conditions for Q to have a good decomposition and a characterization of Q with a good decomposition when T is a strong semicomplete digraph and each H_i is an arbitrary digraph with at least two vertices. For digraph products, we prove the following: (a) if k≥ 2 is an integer and G is a strong digraph which has a collection of arc-disjoint cycles covering all vertices, then the Cartesian product digraph G^ k (the kth powers with respect to Cartesian product) has a good decomposition; (b) for any strong digraphs G, H, the strong product G H has a good decomposition.
READ FULL TEXT