$\partial$-invariant path generators for digraphs

Abstract

We study the structure of the space $\hat{I}{\text{c◯}}_3(G)$ of $\partial$-invariant 3-paths in a directed graph $G$. We prove that $\hat{I}{\text{c◯}}_3(G)$ admits a basis consisting of trapezohedral paths $\ddot{I}{„}_m$ ($m\ge 2$) and their merging images. Moreover, we provide an explicit construction of such a basis and, as a consequence, obtain an algorithm with time complexity $O(|V(G){|}^5)$ for computing the dimension and a basis of $\hat{I}{\text{c◯}}_3(G)$ for any finite digraph.

20 pages, 8 figures