Arc-disjoint strong spanning subdigraphs of semicomplete compositions

Jørgen Bang-Jensen, Gregory Gutin*, Anders Yeo

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

A strong arc decomposition of a digraph D=(V,A) is a decomposition of its arc set A into two disjoint subsets A1 and A2 such that both of the spanning subdigraphs D1=(V,A1) and D2=(V,A2) are strong. Let T be a digraph with t vertices u1.....,ut and let H1....,Ht be digraphs such that Hi has vertices ui,j,. 1≤Ji≤ni Then the composition Q=T[H1...,Hi] is a digraph with vertex set (Formula presented.) and arc set (Formula presented.) We obtain a characterization of digraph compositions Q=T[H1...,Ht] which have a strong arc decomposition when T is a semicomplete digraph and each Hi 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[H1..,Ht 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[H1..,Ht, with T semicomplete, whenever such a decomposition exists.

OriginalsprogEngelsk
TidsskriftJournal of Graph Theory
Vol/bind95
Udgave nummer2
Sider (fra-til)267-289
ISSN0364-9024
DOI
StatusUdgivet - okt. 2020

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

  • Citationsformater