A Note on the Number of Edges Guaranteeing a $C_4$ in Eulerian Bipartite Digraphs

Jian Shen, Raphael Yuster

Abstract


Let $G$ be an Eulerian bipartite digraph with vertex partition sizes $m,n$. We prove the following Turán-type result: If $e(G) > 2mn/3$ then $G$ contains a directed cycle of length at most 4. The result is sharp. We also show that if $e(G)=2mn/3$ and no directed cycle of length at most 4 exists, then $G$ must be biregular. We apply this result in order to obtain an improved upper bound for the diameter of interchange graphs.


Full Text: PDF