Arc‐disjoint strong spanning subdigraphs of semicomplete compositions. Issue 2 (13th April 2020)

• Record Type: Journal Article
• Authors: Bang‐Jensen, Jørgen; Gutin, Gregory; Yeo, Anders
• Is Part Of: Journal of graph theory. Volume 95:Issue 2(2020)
• Page Start: 267
• Page End: 289
• Publication Date: 2020-04-13
• Subjects: decomposition into strong spanning subdigraphs -- digraph composition -- semicomplete digraph -- strong spanning subdigraph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22568
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A strong arc decomposition of a digraph D = ( V, A ) is a decomposition of its arc set A into two disjoint subsets A 1 and A 2 such that both of the spanning subdigraphs D 1 = ( V, A 1 ) and D 2 = ( 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 ⋃ i = 1 t V ( H i ) = { u i, j i ∣ 1 ≤ i ≤ t, 1 ≤ j i ≤ n i } and arc set ⋃ i = 1 t A ( H i ) ⋃ ⋃ u i u p ∈ A ( T ) { u i j i u p q p ∣ 1 ≤ j i ≤ n i, 1 ≤ q p ≤ n p } . We obtain a characterization of digraph compositions Q = T [ H 1, …, H t ] which have a strong arc decomposition when T is a semicomplete digraph and each H i is an arbitrary digraph. Our characterization generalizes a characterization by Bang‐Jensen and Yeo (2003) of semicomplete digraphs with a strong arc decomposition and solves an open problem by Sun, Gutin, and Ai (2019) on strong arc decompositions of digraph compositions Q = T [ H 1, …, H t ] in which T is semicomplete and each H i is arbitrary. Our proofs are constructive and imply the existence of a polynomial algorithm for constructing a strong arc decomposition of a digraph Q = T [ H 1, …, H t ], with T semicomplete, whenever such a decomposition exists.