Maximal number of directed edges in suitable simple graphs on $n$ vertices without directed triangles.

Question

We consider the class $C$ of directed simple (no multiple edges) graphs having the property that every vertex is reachable by a directed path from every other vertex.

Given an integer $k$, what is the maximal possible number of (directed) edges in a graph of $C$ with $n$ vertices such that there are no directed cycles of length $\leq k$?

For $k=2$ this means simply that the existence of an edge from $v$ to $w$ forbids the existence of an edge from $w$ to $v$ and one can thus choose arbitrary orientions (giving rise to a graph in $C$) on the edges of the complete unoriented graph.

For $k=3$, one has also to forbid oriented triangles which is not possible by orienting all edges of a complete graph on $n\geq 3$ vertices such that the result is in $C$.

On the other hand, there are of course no triangles by choosing arbitrary orientations (giving rise to an element in $C$) of a complete bipartite graph. There are thus such graphs having roughly $n^2/4$ directed edges.

There should be better upper and lower bounds.

Motivation: G. Higman (A finitely generated infinite simple group. J. London Math. Soc. 26, (1951). 61--64) constructed finitely generated infinite simple groups by considering quotients of the finitely presented group $$\langle g_1,\dots,g_n|g_{i-1}^{-1}g_ig_{i-1}=g_i^2\rangle$$ where indices are modulo $n$.

This group is trivial for $n=2,3$ and infinite for $n\geq 4$. Given a directed graph, one can consider the corresponding group-presentation with generators corresponding to vertices and directed edges corresponding to relations $a^{-1}ba=b^2$. The triviality of the group constructed by Higman associated to $n=2,3$ implies that we want to avoid oriented cycles of length $\leq 3$ when searching for interesting examples.

Answer 1

Updated 4/17/11:

(Originally, this answer contained a different proof of the result below for $k=3$. Not only did the proof not generalize, but it was wrong.)

The maximum number of edges in a strongly-connected digraph with $n \geq k+1$ vertices and no cycles of length at most $k$ is $${\binom{n}{2}} - n(k-2) + \frac{(k+1)(k-2)}{2}.$$ (A digraph where every vertex is reachable from every other vertex by a directed path is called strongly connected.)

Gordon Royle conjectured this bound an gave an example achieving it for $k=3$. For general $k$ and $n$ the bound is attained by the following construction, almost identical to the one provided by Nathann Cohen in the comments:

Let vertices $x_1,x_2,\ldots,x_{n-k+2}$ form a transitive tournament with $x_i \to x_j$ being an edge for all $1 \leq i < j \leq n-k+2$. Now delete the edge $x_1 \to x_{n-k+2}$ and replace it with a path $x_{n-k+2} \to x_{n-k+3} \to \ldots \to x_n \to x_1$. (The vertices $x_{n-k+3},\ldots, x_n$ will have in-degree one and out-degree one in the resulting graph.)

It remains to prove that the above number is a valid upper bound. The proof is by induction on $n$.

Simple counting shows that the bound is valid if $G$ is a directed cycle. It is tight if $G$ is a cycle of length $k+1$. Assume now that $G$ is not a cycle. Then there exist $\emptyset \neq X \subsetneq V(G)$ such that $G|X$ is strongly connected. (For example, one can choose the vertex set of any induced cycle in $G$.) Choose $X$ maximal subject to the above. Let $u \to v_1$ be an edge of $G$ with $u \in X$, $v_1 \not \in X$, and let $P$ be a shortest path in $G$ from $v_1$ to $X$. Let $P=v_1 \to v_2 \to \ldots \to v_l \to w$.

Note that adding to $G|X$ any path starting and ending in $X$ produces a strongly connected digraph. It follows from the choice of $X$ that any non-trivial such path must include all the vertices in $V(G)-X$. In particular, if $l\geq 3$, $v_2,\ldots,v_{l-1}$ have no neighbors in $X$.

Let us further assume that $u$ and $w$ are chosen so that the directed path $Q$ from $w$ to $u$ in $G|X$ is as short as possible. (Perhaps, $w=u$.) Then $V(P) \cup V(Q)$ induces a cycle in $G$, and so $v_1$ and $v_l$ have at least $k-2$ non-neighbors on $V(P) \cup V(Q)$. At least $k-l$ of those non-neighbors are in $X$ if $l\geq 2$. Therefore there are at least $k-2$ non-edges (pairs of non-adjacent vertices) between $X$ and $V(G)-X$ if $l=1$, and at least $$2(k-l)+(l-2)(k+1) \geq l(k-2)$$ non-edges if $l \geq 2$. By the induction hypothesis there are at least $|X|(k-2)- \frac{(k+1)(k-2)}{2}$ non-edges between vertices of $X$, and therefore at least $$(l+|X|)(k-2)- \frac{(k+1)(k-2)}{2}=n(k-2) - \frac{(k+1)(k-2)}{2}$$ non-edges in total, as desired.

Answer 2

OK, I think that a lower bound for the $k=3$ case is $(n^2-3n+4)/2$ and (a small amount of) computational evidence suggests that this is the right number.

I'll start with a directed cycle on $0 \rightarrow 1 \rightarrow 2\rightarrow \cdots \rightarrow (n-1) \rightarrow 0$ [$n$ edges so far, and strong connectivity is guaranteed] and will add some further edges... every edge $i \rightarrow j$ that will be added will have $i < j$, and since the only edge in the entire graph that has $i > j$ is the edge $(n-1) \rightarrow 0$, any directed triangle must use this edge - call this the "special edge".

Now add the following edges:

• join $0$ to $2, 3, \ldots, n-3$ [$n-4$ edges added]
• join $1$ to $3, 4, \ldots, n-3$ [$n-4$ edges added]
• join $2$ to $4, 5, \ldots, n-3$ [$n-5$ edges added]
• join $3$ to $5, 6, \ldots, n-3$ [$n-6$ edges added]
• ...
• join $n-4$ to $n-3$ [1 edge added]

Now vertex $n-$1 has in-degree 1 (from $n-$2) and out-degree 1 (to vertex 0) and so any directed triangle using the special edge must use the edge $(n-2)\rightarrow (n-1)$ as well. But there is no edge from 0 to $n-2$ by construction and so there are no directed triangles.

Count 'em all up and you get $(n^2-3n+4)/2$.

I've tested this for $n$ up to 8 and the numbers work out... but there is far from a unique graph with that number of edges and so I cannot see any obvious proof