Cycles in dense digraphs

Abstract

Let G be a digraph (without parallel edges) such that every directed cycle has length at least four; let $\beta (G)$ denote the size of the smallest subset X in E(G) such that $G\X$ has no directed cycles, and let $\gamma (G)$ be the number of unordered pairs {u,v} of vertices such that u,v are nonadjacent in G. It is easy to see that if $\gamma (G)=0$ then $\beta (G)=0$; what can we say about $\beta (G)$ if $\gamma (G)$ is bounded? We prove that in general $\beta (G)$ is at most $\gamma (G)$. We conjecture that in fact $\beta (G)$ is at most $\gamma (G)/2$ (this would be best possible if true), and prove this conjecture in two special cases: 1. when V(G) is the union of two cliques, 2. when the vertices of G can be arranged in a circle such that if distinct u,v,w are in clockwise order and uw is a (directed) edge, then so are both uv and vw.

Cited by in corpus (1)

• Heights in finite projective space, and a problem on directed graphs