Article ID Journal Published Year Pages File Type
4647235 Discrete Mathematics 2015 12 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,