Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs
by
Jian Shen
Southwest Texas State University, San Marcos, TX 78666
Coauthors: Richard Brualdi, University of Wisconsin - Madison, Madison, WI 53706

Let R=(r₁, ... , r_m) and S=(s₁, ... , s_n) be non-negative integral vectors with \sumr_i=\sums_j. Let A (R, S) denote the set of all m ×n {0, 1}-matrices with row sum vector R and column sum vector S. Suppose A (R, S) =/= \emptyset. The interchange graph G(R, S) of A (R, S) was defined by Brualdi in 1980. It is the graph with all matrices in A (R, S) as its vertices and two matrices are adjacent provided they differ by an interchange matrix. Brualdi conjectured that the diameter of G(R, S) cannot exceed mn/4.

A digraph G=(V, E) is called Eulerian if, for each vertex u in G, the outdegree and indegree of u are equal. We first prove that any bipartite Eulerian digraph with vertex partition sizes m, n, and with more than (\surd{17} -1) mn/ 4 ( \approx 0.78 mn) arcs contains a cycle of length at most 4. As an application of this, we show that the diameter of G(R, S) cannot exceed (3+\surd{17}) mn /16  ( \approx 0.445 mn). The latter result improves a recent upper bound on the diameter of G(R, S) by Qian.

Finally, we present some open problems concerning the girth and the maximum number of arc disjoint cycles in an Eulerian digraph.

Date received: April 20, 2001