<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume9 Issue1" %>
Packing 4-Cycles in Eulerian and Bipartite Eulerian Tournaments with an Application to Distances in Interchange Graphs
Raphael Yuster
Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel
Annals of Combinatorics 9 (1) p.117-124 March, 2005
AMS Subject Classification: 05C20, 05C70
We prove that every Eulerian orientation of Km, n contains arcdisjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument, this result is used to prove that every regular tournament with n vertices contains n2(1-o(1)) arc-disjoint directed 4-cycles. The result is also used to provide an upper bound for the distance between two antipodal vertices in interchange graphs.
Keywords: tournaments, packing, cycles, interchange graphs


1. N. Alon and J.H. Spencer, The Probabilistic Method, Second Edition, Wiley, New York, 2000.

2. B. Bollobás, Extremal Graph Theory, Academic Press, 1978.

3. L.W. Beineke, Cycles in bipartite tournaments, J. Combin. Theory Ser. B 32 (1982) 140--145.

4. R.A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra Appl. 33 (1980) 159--231.

5. R.A. Brualdi and J. Shen, Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs, J. Combin. Theory Ser. B 85 (2002) 189--196.

6. J. Kahn, Asymptotically good list colorings, J. Combin. Theory, Ser. A 73 (1996) 1--59.

7. A. Kotzig, Sur le nombre des 4-cycles dans un tournoi, Mat. ČSloven. Akad. Vied 18 (1968) 247--254.

8. B.D. McKay, The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs, Combinatorica 10 (1990) 367--377.

9. P. Rowlinson, On 4-cycles and 5-cycles in regular tournaments, Bull. London Math. Soc. 18 (1986) 135--139.

10. H.J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math. 9 (1957) 371--377.

11. J. Shen and R. Yuster, A note on the number of edges guaranteeing a C4 in Eulerian bipartite digraphs, Electron. J. Combin. 9 (2002) #N6.

12. D.W. Walkup, Minimal interchanges of (0,1)-matrices and disjoint circuits in a graph, Canad. J. Math. 17 (1965) 831--838.