Abstract:A transitive tournament is an acyclic orientation of a complete graph. We study decompositions and packings of the transitive tournament \(TT_n\) into connected two-arc motifs. The three motifs considered are chains, colliders, and forks, which are also fundamental local configurations in directed acyclic graphs. We first construct decompositions of \(TT_n\) into mixtures of these motifs whenever such decompositions exist. We then consider the corresponding pure packing problem for each individual motif. For \(H\) equal to a chain, a collider, or a fork, we determine the maximum number of arc-disjoint copies of \(H\) in \(TT_n\). These results give a precise extremal description of two-arc motif packings in transitive tournaments and suggest further questions on motif decompositions in broader classes of directed acyclic graphs.
| Comments: | 17 pages, 6 figures |
| Subjects: | Combinatorics (math.CO) |
| MSC classes: | 05C20, 05C51, 05C20 |
| Cite as: | arXiv:2605.24801 [math.CO] |
| (or arXiv:2605.24801v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.24801 arXiv-issued DOI via DataCite (pending registration) |
From: Ajani De Vas Gunasekara [view email]
[v1]
Sun, 24 May 2026 01:13:13 UTC (15 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。