Arc-disjoint strong spanning subdigraphs of semicomplete compositions

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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

37 Downloads (Pure)

Abstract

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.

Original languageEnglish
JournalJournal of Graph Theory
Volume95
Issue number2
Pages (from-to)267-289
ISSN0364-9024
DOIs
Publication statusPublished - Oct 2020

Keywords

  • decomposition into strong spanning subdigraphs
  • digraph composition
  • semicomplete digraph
  • strong spanning subdigraph

Fingerprint

Dive into the research topics of 'Arc-disjoint strong spanning subdigraphs of semicomplete compositions'. Together they form a unique fingerprint.

Cite this