Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs

2003/10/26 by Raphael Yuster, Yuster, Raphael
Computer Science · Engineering · Mathematics · #05C20 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05C20 #msc:05C70

paper · pdf · doi:10.48550/arxiv.math/0310411

9 Pages

arxiv created 2003/10/26 · openalex publication_date 2003/10/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that every Eulerian orientation of K_m,n contains (1)/(4+√(8))mn(1-o(1)) arc-disjoint 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 (1)/(8+√(32))n²(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.

Related

• Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments
• A Note on Arc-Disjoint Cycles in Bipartite Tournaments
• On the existence of specified cycles in bipartite tournaments
• Coxeter interchange graphs
• About the number of oriented Hamiltonian paths and cycles in tournaments