𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Disjoint Cycles in Eulerian Digraphs and the Diameter of Interchange Graphs

✍ Scribed by Richard A. Brualdi; Jian Shen

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
87 KB
Volume
85
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

denote the set of all m Γ— n {0, 1}-matrices with row sum vector R and column sum vector S. Suppose A(R, S) ] ". 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 Β₯ V, 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 (17 -1) mn/4 (% 0.78mn) 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+17) mn/16 (% 0.445mn). 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.

πŸ“œ SIMILAR VOLUMES

On the superconnectivity and the conditi
On the superconnectivity and the conditional diameter of graphs and digraphs
✍ Carmona, A.; FοΏ½brega, J. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 142 KB πŸ‘ 2 views

It has been proved that if the diameter D of a digraph G satisfies D Υ… 2ᐉ Οͺ 2, where ᐉ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D Υ… 2ᐉ Οͺ 1, then G is edge-superconnected. In this paper, we studied some similar condi

On the connectivity and the conditional
On the connectivity and the conditional diameter of graphs and digraphs
✍ Balbuena, C.; Carmona, A.; FοΏ½brega, J.; Fiol, M. A. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 771 KB

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D 5 21 -1, then G has maximum connectivity ( K = 6 ) .

Disjoint Cycles in Directed Graphs on th
Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle
✍ G.L. Ding; A. Schrijver; P.D. Seymour πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 203 KB

We give necessary and sufficient conditions for a directed graph embedded on the torus or the Klein bottle to contain pairwise disjoint circuits, each of a given orientation and homotopy, and in a given order. For the Klein bottle, the theorem is new. For the torus, the theorem was proved before by

Edge disjoint Hamilton cycles in sparse
Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
✍ BollobοΏ½s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 175 KB πŸ‘ 3 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for

Disjoint circuits in the cartesian produ
Disjoint circuits in the cartesian product of two directed cycles
✍ Stephen Curran πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 291 KB

## Abstract We show that the Cartesian product of two directed cycles __Z__~__a__~ X __Z__~__b__~ has __r__ disjointly embedded circuits __C__~1~, __C__~2~, ⃛, __C__~r~ with specified knot classes knot__(C~i~) = (m~i~, n~i~)__, for __i__ = 1, 2, ⃛, __r__, if and only if there exist relatively prime