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

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

2003-10-26

arxiv.org/abs/math/0310411v1

Mathematics

Combinatorics

9 Pages

Scientific paper

We prove that every Eulerian orientation of $K_{m,n}$ contains $\frac{1}{4+\sqrt{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 $\frac{1}{8+\sqrt{32}}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.

Affiliated with

Also associated with

No associations

Rating

Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293554