A cage is a smallest undirected graph with the following two properties (for some constants $r,g$):

  • Each node has exactly $r$ neighbors;
  • The smallest cycle has exactly $g$ nodes.

When $r=2$ a cage is just a cycle with $g$ nodes, so cages usually become interesting only for $r\geq 3$.

I am interested in a "directed cage": a smallest directed graph with the following properties:

  • Each node has exactly $r$ outgoing edges;
  • The smallest undirected cycle (- a cycle in which the edge directions are ignored) has exactly $g$ nodes.

MY QUESTION IS: Is anything known about such "directed cages"?

Specifically: how many nodes are needed for a directed cage when $r=2$, as a function of $g$?

  • $\begingroup$ For $r=2$, there is an obvious graph with $2(g+1)$ vertices. Can you do better? In the other direction, the case $g=3$ includes the Caccetta–Haggkvist conjecture so it is very hard. $\endgroup$ – Brendan McKay Aug 22 '16 at 12:54
  • $\begingroup$ @BrendanMcKay In the obvious graph with $2(g+1)$ vertices, does the smallest directed cycle have $g$ nodes? Or the smallest undirected cycle? $\endgroup$ – Erel Segal-Halevi Aug 22 '16 at 17:38
  • $\begingroup$ Are your graphs strictly directed? In other words, do you allow the presence of both an edge and its reverse? If yes, then it seems to me that a cycle of length 2 is the answer. (Where we think of the cycle as having edges in both direction.) If no, then it seems to me that the answer is simply the size of an undirected (4,g)-cage. Indeed, in this case, the underlying graph of the digraph is 4-valent and has girth g, while any 4-valent graph of girth g can have its edges oriented to yield a directed graph of out-valency 2 (using an Eulerian circuit say). $\endgroup$ – verret Aug 22 '16 at 21:07
  • 1
    $\begingroup$ @Erel: Please define what you mean by an "undirected cycle" in a directed graph. If you just mean that the edges of the cycle don't need to be directed consistently (some can point one way and some the other way) then the fact you are dealing with digraphs is almost irrelevant, as in Verret's comment. $\endgroup$ – Brendan McKay Aug 23 '16 at 0:11
  • 1
    $\begingroup$ @BrendanMcKay I can't think of any other natural definition... $\endgroup$ – verret Aug 23 '16 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.