Discrete Morse theory on digraphs (Q2071461)

Let \(G\) be a directed graph (or digraph) on a vertex set \(V\). A discrete Morse function on \(G\) is defined to be a function \(f \colon V \to [0, +\infty)\) such that the following two conditions are verified for every directed path \(\alpha\): (i) there is at most one directed path obtained from \(\alpha\) by adding a vertex \(v \in f^{-1}(0)\) somewhere along the path; there is at most one directed path obtained from \(\alpha\) by removing a vertex \(v' \in f^{-1}(0)\) (cf.\ Definition 2.1). In Theorem 2.12, the authors prove that a discrete Morse function \(f\) on \(G\) is also a discrete Morse function on the transitive closure \(\overline G\) of \(G\) if and only if the following condition (*) is satisfied: for each vertex \(v \in V\), there exists at most one vertex \(w \in f^{-1}(0)\) in all directed paths starting or ending at \(v\). Under condition (*) and additional conditions, the authors prove that the path homology of \(G\) is isomorphic to the homology of a suitably defined Morse complex. They also give examples of computation of the path homology of digraphs.