3
$\begingroup$

Let G be a finite directed graph (allowing multiple edges). We define a cycle (as usual) to be a sequence of edges $e_0, e_1, \dots, e_{n-1}$ (up to cyclic permutation) such that the terminal vertex of $e_i$ is the initial vertex of $e_{i+1}$ (indexing modulo $n$). A cycle is minimal if no vertex appears more than once among the initial vertices of the sequence.

We can assume that $G$ is strongly connected, that is, there is a directed path between any two vertices. For my purposes, we can also assume that every vertex has at least two out-going edges and at least two incoming edges (in fact, we can reduce to this).

Finally, here is the question. Does there exist such a directed graph such that for every edge $e$, whenever $D$ and $E$ are distinct minimal cycles containing $e$, there exists a third (distinct) minimal cycle $C$ with $C \subset D \cup E$ and $e$ not in $C$. [That $D \cup E$ even contains a third minimal cycle is fairly strong on its own.]

The question arises in the classification of dynamical systems on zero-dimensional spaces, and also in the (ordered) cohomology of graphs. (This requires a chain of explanations.)

$\endgroup$
3
$\begingroup$

The proposition is true vacuously for a directed cycle, or a directed graph in which every biconnected component is a cycle. In order to get such a graph and also meet your assumptions on the minimum indegree and out-degree, one would have to allow self-loops.

For any other graph, it's false. For, let $G$ be biconnected (otherwise split into components and treat each one separately) and not itself a single cycle. Then $G$ has a directed open ear decomposition. Let $E$ be the first ear (a simple directed cycle) and $F$ be the second ear (a simple path starting and ending at different vertices of $E$, and otherwise disjoint from $E$). Let $D$ be the cycle consisting of $F$ together with the path in $E$ connecting its endpoints. Then $D$ and $E$ share at least one edge $e$, but there is no third minimal cycle in $D\cup E$.

$\endgroup$

Your Answer

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

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