Search

For an oriented graph G with n vertices, let f(G) denote the minimum number of transitive subtournaments that decompose G. We prove several results on f(G). In particular, if G is a tournament then f(G)n2/3000. For general G we prove that f(G)⩽⌊n2/3⌋ and this is tight. Some related parameters are also considered.

We prove that a tournament with n vertices has more than 0.13 n 2 ( 1 + o ( 1 ) ) edge-disjoint transitive triples. We also prove some results on the existence of large packings of k-vertex transitive tournaments in an n-vertex tournament. Our proofs combine probabilistic arguments and some powerful packing results due to Wilson and to Frankl and Rodl.

A classfication of 2-arc-transitive circulant digraphs is given.