A complete characterization of split digraphs with a strong arc decomposition
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911977212739584 |
|---|---|
| author | Ai, Jiangdong He, Fankang Li, Zhaoxiang Qin, Zhongmei Wang, Changxin |
| author_facet | Ai, Jiangdong He, Fankang Li, Zhaoxiang Qin, Zhongmei Wang, Changxin |
| contents | 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_02260 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A complete characterization of split digraphs with a strong arc decomposition Ai, Jiangdong He, Fankang Li, Zhaoxiang Qin, Zhongmei Wang, Changxin Combinatorics 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]. |
| title | A complete characterization of split digraphs with a strong arc decomposition |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.02260 |