# Fundamental Semigroup of a Directed Graph

For a finite graph $G$ it is quite easy to calculate the fundamental group. You just choose a maximal tree and then since trees are contractible, you get that the fundamental group of a finite graph is the free group $F_n$, where $n$ is the number of edges that is not contained in the maximal tree.

If the graph is directed, it is still possible to talk about loops (a cycle in a directed graph is a well-defined concept) and we can still multiply different loops by concatenation, so we can talk about a similar algebraic invariant. Since we do not have any inverses, the result is a monoid. Actually, since there will be no torsion and there are no homotopies, it will be a free monoid.

I wonder whether there is a easy way to calculate the fundamental semigroup (if the name is appropriate) of a directed graph. Clearly, the maximal tree trick does not work here.

• So you're asking for a simple way to count the number of directed paths from a vertex $v$ to itself that do not pass through $v$ in the middle? Commented Dec 22, 2016 at 6:15
• Yes. I guess it is more of a combinatorial question than a topological question. But I would be happier if there would be a topological solution, just like contracting a subspace (which is of course impossible in this case). Commented Dec 22, 2016 at 17:59

We can find generators for the fundamental monoid as follows. Choose a vertex $v$ in the directed graph $G$ and construct two directed trees as follows. For the first tree, the the breadth-first search tree rooted at $v$. (This is our out-tree.) The second tree is chosen so that each vertex $w$ in the tree is joined by a directed path from $w$ to $v$; it is maximal with this property. This is our in-tree.
Now any arc of $G$ that does not belong to one of the two trees determines a unique closed walk starting at $v$ - a walk in the out tree to the initial vertex of the arc, cross along the arc, then return to $v$ via the in-tree. It is immediate that the arcs not in either tree generate the fundamental monoid of $G$.
• This answer isn't true. Let v,w be vertecies. Assume that there is a closed path $\gamma$ beginning and ending at w that doesn't pass through v. Let $\alpha$ be a simple path from v to w and $\beta$ a simple path from w to v. There are infinite different paths $\alpha *\gamma^{n} *\beta$ . The method described can account for at most one. It is clear that $\left( \alpha *\gamma *\beta \right)^{n} \neq \alpha *\gamma^{n} *\beta$ Commented Jun 26, 2023 at 14:08