8
$\begingroup$

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.

$\endgroup$
5
  • 6
    $\begingroup$ Without the connectivity constraint I would have said "orient transitively the edges of a complete graph" to have $\binom n 2$ edges and no directed cycle at all. To respect the connectivity constraint you can always add a direct path of length k+1 from the element of maximum indegree to the element of minimum indegree. Then you have for each $k$ a "family of digraphs with roughly $\binom n 2$ edges and no circuit of size $\leq k$." $\endgroup$ Mar 24, 2011 at 10:33
  • 1
    $\begingroup$ Your question makes me think of the Caccetta-Haggkvist conjecture though, even if it does not contain in its definition any connectivity requirement. math.uiuc.edu/~west/openp/cacchagg.html $\endgroup$ Mar 24, 2011 at 10:33
  • $\begingroup$ The Caccetta-Haggkvist conjecture is probably the right setting for this kind of problems. $\endgroup$ Mar 24, 2011 at 11:22
  • $\begingroup$ Do you insist that if (u,v) is a directed edge, then (v,u) is not present? $\endgroup$ Mar 24, 2011 at 13:03
  • $\begingroup$ gordon-royle, this is ruled out for $k \geq 2$ by the condition that there be no 2-cycles. $\endgroup$
    – JBL
    Mar 24, 2011 at 13:13

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice work. Glad you finished it off. $\endgroup$ Apr 12, 2011 at 23:24
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.