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

raphy@research.haifa.ac.il

Annals of Combinatorics 9 (1) p.117-124 March, 2005

Abstract:

We prove that every Eulerian orientation of *K*^{m, 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 *n*^{2}(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.

References:

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 C_{4} 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.