Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647235 | Discrete Mathematics | 2015 | 12 Pages |
Abstract
For a tournament TT, let ν3(T)ν3(T) denote the maximum number of pairwise edge-disjoint triangles (directed cycles of length 3) in TT. Let ν3(n)ν3(n) denote the minimum of ν3(T)ν3(T) ranging over all regular tournaments with nn vertices (nn odd). We conjecture that ν3(n)=(1+o(1))n2/9ν3(n)=(1+o(1))n2/9 and prove thatn211.43(1−o(1))≤ν3(n)≤n29(1+o(1)) improving upon the best known upper bound of n2−18 and lower bound of n211.5(1−o(1)). The result is generalized to tournaments where the indegree and outdegree at each vertex may differ by at most βnβn.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Islam Akaria, Raphael Yuster,