Premium
Arc‐disjoint strong spanning subdigraphs of semicomplete compositions
Author(s) -
BangJensen Jørgen,
Gutin Gregory,
Yeo Anders
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22568
Subject(s) - digraph , combinatorics , disjoint sets , mathematics , arc (geometry) , vertex (graph theory) , mathematical proof , characterization (materials science) , constructive , decomposition , discrete mathematics , set (abstract data type) , graph , chemistry , computer science , process (computing) , materials science , geometry , organic chemistry , programming language , nanotechnology , operating system
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 iu 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.