### Abstrakt

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,}. 1≤J_{i}≤n_{i} Then the composition Q=T[H_{1}...,H_{i}] is a digraph with vertex set (Formula presented.) and arc set (Formula presented.) 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 (Formula presented.) 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.

Originalsprog | Engelsk |
---|---|

Tidsskrift | Journal of Graph Theory |

Vol/bind | 95 |

Udgave nummer | 2 |

Sider (fra-til) | 267-289 |

ISSN | 0364-9024 |

DOI | |

Status | Udgivet - okt. 2020 |

## Fingeraftryk Dyk ned i forskningsemnerne om 'Arc-disjoint strong spanning subdigraphs of semicomplete compositions'. Sammen danner de et unikt fingeraftryk.

## Citationsformater

*Journal of Graph Theory*,

*95*(2), 267-289. https://doi.org/10.1002/jgt.22568