Decomposing oriented graphs into transitive tournaments (Q817766)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposing oriented graphs into transitive tournaments |
scientific article |
Statements
Decomposing oriented graphs into transitive tournaments (English)
0 references
20 March 2006
0 references
If \(G\) is an oriented graph with \(n\) vertices, let \(f(G)\) denote the least number of arc-disjoint transitive subtournaments whose union includes all arcs of \(G\). The author shows that, in general, \(f(G)\leq\lfloor n^2/3\rfloor\) and that equality holds when \(G\) has at most \(n^2/3\) arcs. He also shows, among other things, that if \(G\) is a tournament, then \((n^2/3000)(1+ o(1))< f(G)< (5n^2/21)(1+ o(1))\).
0 references
decomposition
0 references