A complete characterization of split digraphs with a strong arc decomposition

Jiangdong Ai; Fankang He; Zhaoxiang Li; Zhongmei Qin; Changxin Wang

paper

A complete characterization of split digraphs with a strong arc decomposition

arXiv:2408.02260

Abstract

A \textbf{strong arc decomposition} of a (multi-)digraph $D (V, A)$ is a partition of its arc set $A$ into two disjoint arc sets $A_{1}$ and $A_{2}$ such that both of the spanning subdigraphs $D (V, A_{1})$ and $D (V, A_{2})$ are strong. In this paper, we fully characterize all split digraphs that do not have a strong decomposition. This resolves two problems proposed by Bang-Jensen and Wang and contributes to a series of efforts aimed at addressing this problem for specific graph classes. This work continues the research on semicomplete composition [Bang-Jensen, Gutin and Yeo, J. Graph Theory, 2020]; on locally semicomplete digraphs [Bang-Jensen and Huang, J. Combin. Theory Ser. B, 2010]; on a type of tournaments [Bang-Jensen and Yeo, Combinatorica, 2004].

34 pages