© Wuhan University 2022

0 Introduction

Digraphs are important topological models in complex networks and the homology groups of digraphs can reveal the topological and geometric characteristics of complex networks. Among many approaches for constructing (co) homology of digraphs^{[1, 2]}, a natural and important homology theory on digraphs is path homology introduced by Grigor'yan et al, which theory has been systematically developed with fruitful results^[3-9]. In this paper, we consider the discrete Morse theory based on the path homology of digraphs.

Let $G=(V(G),E(G))$ be a digraph where $V(G)$ is the vertex set of $G$ and $E(G)$ is the directed edge set of $G$. For any directed edge $(u,v)\in E(G)$, it can be denoted as $u\to v$. $G$ is called transitive, if $u\to v$ and $v\to w$ are two directed edges of G, then $u\to w$ is a directed edge of $G$. The smallest transitive digraph containing $G$ is called the transitive closure of $G$, denoted as $\overline{G}$.

Let $R$be a commutative ring with unit. An elementary n-path is a sequence $v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n$ of $n+\mathrm{1}$ vertices in $V(G)$, $n\ge \mathrm{0}$. Let ${\Lambda }_n(V(G))$ be the $R$-module consisting of all the formal linear combinations of the n-paths on $V(G)$. The boundary map

${\partial }_n:{\Lambda }_n(V(G))\to {\Lambda }_{n-\mathrm{1}}(V(G))$

is defined as

${\partial }_n(v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n)={\displaystyle \sum _{i=\mathrm{0}}^n}{(-\mathrm{1})}^i{d}_i(v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n)$

where $d_i$ is the i-th face map

$d_i:{\Lambda }_n(V(G))\to {\Lambda }_{n-\mathrm{1}}(V(G))$

such that

$d_i(v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n)=v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots {\widehat{v}}_i\cdots v_n.$

Here ${\widehat{v}}_i$ means omission of the vertex $v_i$. Then ${\partial }_n{\partial }_{n+\mathrm{1}}=\mathrm{0}$ for each $n\ge \mathrm{0}$. Hence,$\{{\Lambda }_n(V(G)),{\partial }_n{\}}_{n\ge \mathrm{0}}$ is a chain complex, simply denoted as $\Lambda (V(G))$ if there is no ambiguity.

An allowed elementary n-path is an elementary n-path $v_{\mathrm{0}}\cdots v_i{v}_{i+\mathrm{1}}\cdots v_n$ such that $v_i\ne v_{i+\mathrm{1}}$ and $v_i\to v_{i+\mathrm{1}}$ is a directed edge of $G$ for each $\mathrm{0}\le i\le n-\mathrm{1}$. Let $P_n(G)$ be the free $R$-module consisting of all the formal linear combinations of allowed elementary n-paths on $G$. Then $P_n(G)$ is a submodule of ${\Lambda }_n(V(G))$. However, in general, $\{P_n(G),{\partial }_n{\}}_{n\ge \mathrm{0}}$ is not a subchain complex of $\Lambda (V(G))$. Consider the sub-$R$-module

${\mathrm{\Omega }}_n(G)=\{x\in P_n(G)|\partial x\in P_{n-\mathrm{1}}(G)\}$

of $P_n(G)$. Then ${\partial }_n{\mathrm{\Omega }}_n(G)\subseteq {\mathrm{\Omega }}_{n-\mathrm{1}}(G)$. The path homology groups of $G$ are defined as the homology groups of chain complex $\{{\mathrm{\Omega }}_n(G),{\partial }_n\}$, denoted as $H_{\mathrm{*}}(G;R)$.

In topological data analysis, we are concerned with the calculation and simplification of homology groups. Morse theory is just an important tool to simplify the calculation of homology groups. In 1998, Forman^[10] extended Morse theory on smooth manifolds to cell complexes and simplicial complexes. And based on this study, Forman studied discrete Morse theory, cohomology card product, Witten Morse theory and other related problems^[11-13]. From 2007 to 2009, Ayala et al^[14-17] studied the discrete Morse theory on graphs by using the discrete Morse theory of cell complexes and simplicial complexes given by Forman. Inspired by these, we studied the discrete Morse theory on digraphs^[18-20].

In this paper, we study the discrete Morse theory on join of digraphs, hoping to give the discrete Morse theory of join by requiring the two factors constituting the connection to meet certain conditions, rather than directly limiting the join.

Let $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ be two digraphs where $G_{\mathrm{1}}=(V(G_{\mathrm{1}}),E(G_{\mathrm{1}}))$ and $G_{\mathrm{2}}=(V(G_{\mathrm{2}}),E(G_{\mathrm{2}}))$. Suppose $V(G_{\mathrm{1}})$ and $V(G_{\mathrm{2}})$ are disjoint. Then $E(G_{\mathrm{1}})$ and $E(G_{\mathrm{2}})$ are disjoint as well. The join of $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ is a digraph $G=G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}$ such that

$•$ the set of vertices of the digraph $G$ is $V(G_{\mathrm{1}})\bigcup V(G_{\mathrm{2}})$;

$•$ the set of directed edges of the digraph $G$ is $E(G_{\mathrm{1}})\bigcup E(G_{\mathrm{2}})\bigcup \{(u,v)|u\in V(G_{\mathrm{1}}),v\in V(G_{\mathrm{2}})\}$.

The paper is organized as follows. In Section 1, we review the definition and some properties of discrete Morse functions on digraphs. In Section 2, we give some auxiliary results for main theorems in Lemma 5 and Lemma 8. Finally, in Section 3, we prove the main theorems of this paper.

Let $G$ be a digraph and $f:V(G)\to [\mathrm{0},+\mathrm{\infty })$ a discrete Morse function on $G$ as defined in Definition 1. Define an $R$-linear map $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{d}f:P_n(G)\to P_{n+\mathrm{1}}(G)$ such that for any allowed elementary n-path $\alpha$ on $G$,

$(\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{d}f)(\alpha )=-<\partial \gamma ,\alpha >\gamma$

where $\gamma >\alpha$ and $f(\gamma )=f(\alpha )$. Otherwise, $(\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{d}f)(\alpha )=\mathrm{0}$^[10]. We call $\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{d}f$ the (algebraic) discrete gradient vector field of $f$ on $G$, denoted as $V_f$ , abbreviated as $V$. The discrete gradient flow is defined as

$\Phi =\mathrm{I}\mathrm{d}+\partial V+V\partial$

Here Id is the identity map from $P_n(G)$ to $P_n(G)$.Correspondingly, the discrete Morse function, the (algebraic) discrete gradient vector field and the discrete gradient flow of a transitive digraph are denoted as $\overline{f}$, $\overline{V}$ and $\overline{\Phi }$, respectively.

The main theorems of this paper are as follows.

Theorem 1   Let $G=G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}$ and $f{}_{\mathrm{1}}{}^{}$,$f{}_{\mathrm{2}}{}^{}$ discrete Morse functions on $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ , respectively. Let $f$ be the discrete Morse function on $G$ determined by $f{}_{\mathrm{1}}{}^{}$ and $f{}_{\mathrm{2}}{}^{}$. Suppose $\mathrm{\Omega }(G_i)$ is ${\overline{V}}_i$-invariant, $i=\mathrm{1,2}$. Then

$H_m(G;R)\cong H_m({\mathrm{\Omega }}_{\mathrm{*}}(G)\bigcap P_{\mathrm{*}}^{\overline{\Phi }}(\overline{G})),m\ge \mathrm{0}$

where $\{P_{\mathrm{*}}^{\overline{\Phi }}(\overline{G}),{\partial }_{\mathrm{*}}\}$ is the subchain complex of $\{P_{\mathrm{*}}(\overline{G}),{\partial }_{\mathrm{*}}\}$ consisting of all $\overline{\Phi }$-invariant chains.

Denote $\mathrm{C}\mathrm{r}\mathrm{i}{\mathrm{t}}_n(G)$ as the free $R$-module consisting of all the formal linear combinations of critical n-paths on $G$. We have that

Theorem 2   Let $G=G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}$. Let $f{}_{\mathrm{1}}{}^{}$ be a function on $G_{\mathrm{1}}$ such that $f_{\mathrm{1}}(v)>\mathrm{0}$ for each vertex $v\in V(G_{\mathrm{1}})$ and $f_{\mathrm{2}}$ a discrete Morse function on $G_{\mathrm{2}}$ with a unique zero-point. Let $f$ be the discrete Morse function on $G$ determined by $f_{\mathrm{1}}$ and $f_{\mathrm{2}}$. Suppose $\mathrm{\Omega }(G_i)$ is ${\overline{V}}_i$-invariant, ${\overline{\Phi }}_i({\alpha }_i)\in \mathrm{\Omega }(G_i)$ for any ${\alpha }_i\in \mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}({\overline{G}}_i)\bigcap P_n(G)$ and $\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}({\overline{G}}_{\mathrm{2}})\bigcap P(G_{\mathrm{2}})=\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}({\overline{G}}_{\mathrm{2}})\bigcap \mathrm{\Omega }(G_{\mathrm{2}})$, $i=\mathrm{1,2}$. Then

$H_m(\{\mathrm{C}\mathrm{r}\mathrm{i}{\mathrm{t}}_n(\overline{G})\bigcap P_n(G),{\tilde{\partial }}_n{\}}_{n\ge \mathrm{0}})\cong H_m(G;R)$

where $\tilde{\partial }=({\overline{\Phi }}^{\mathrm{\infty }}{)}^{-\mathrm{1}}\circ \partial \circ {\overline{\Phi }}^{\mathrm{\infty }}$ and ${\overline{\Phi }}^{\mathrm{\infty }}$ is stabilization map of $\overline{\Phi }$.

1 Preliminaries

In this section, we mainly review the definition and properties of discrete Morse functions on digraphs.

For any allowed elementary paths $\alpha$ and $\beta$, if $\beta$ can be obtained from $\alpha$ by removing some vertices, then we write $\alpha >\beta$ or $\beta <\alpha$.

Definition 1^[20] A map $f:V(G)\to [\mathrm{0},+\mathrm{\infty })$ is called a discrete Morse function on $G$, if for any allowed elementary path $\alpha =v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n$ on $G$, both of the followings hold:

(i) $\#\{{\gamma }^{(n+\mathrm{1})}>{\alpha }^{(n)}|f(\gamma )=f(\alpha )\}\le \mathrm{1}$ ;

(ii) $\#\{{\beta }^{(n-\mathrm{1})}<{\alpha }^{(n)}|f(\beta )=f(\alpha )\}\le \mathrm{1}$

where

$f(\alpha )=f(v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n)={\displaystyle \sum _{i=\mathrm{0}}^n}f(v_i)$

For an allowed elementary path $\alpha$, if in both (i) and (ii), the inequalities hold strictly, then $\alpha$ is called critical. Precisely,

Definition 2   An allowed elementary n-path ${\alpha }^{(n)}$ is called critical, if both of the followings hold:

(i)$\mathrm{\text{'}}$$\#\{{\gamma }^{(n+\mathrm{1})}>{\alpha }^{(n)}|f(\gamma )=f(\alpha )\}=\mathrm{0}$;

(ii)$\mathrm{\text{'}}$$\#\{{\beta }^{(n-\mathrm{1})}<{\alpha }^{(n)}|f(\beta )=f(\alpha )\}=\mathrm{0}.$

It follows from Definition 2 that an allowed elementary $p$-path is not critical if and only if either of the following conditions holds

(i)$″$ there exists ${\beta }^{(n-\mathrm{1})}<{\alpha }^{(n)}$ such that $f(\beta )=f(\alpha )$;

(ii)$″$ there exists ${\gamma }^{(n+\mathrm{1})}>{\alpha }^{(n)}$ such that $f(\gamma )=f(\alpha )$.

A directed loop on $G$ is an allowed elementary path $v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n{v}_{\mathrm{0}}$, $n\ge \mathrm{1}$.

Lemma 1^{[18 , Lemma 2.4]} Let $G$ be a digraph and $f$ a discrete Morse function on $G$. Let $\alpha =v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n{v}_{\mathrm{0}}$ be a directed loop. Then for each $\mathrm{0}\le i\le n$, $f(v_i)>\mathrm{0}$.

Lemma 2^{[18 , Lemma 2.5]} Let $G$ be a digraph and $f$ a discrete Morse function on $G$ as defined in Definition 1. Then for any allowed elementary path on $G$, there exists at most one index such that the value of the corresponding vertex is zero.

Lemma 3^{[19 , Lemma 2.5]} Let $f$ be a discrete Morse function on digraph $G$. Then for any allowed elementary path $\alpha =v_{\mathrm{0}}{v}_{\mathrm{1}}\cdots v_n$ in $G$, (i)$″$ and (ii)$″$ can not both be true.

2 Auxiliary Results for Main Theorems

Let $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ be two digraphs. Suppose $V(G_{\mathrm{1}})$ and $V(G_{\mathrm{2}})$ are disjoint. Then $E(G_{\mathrm{1}})$ and $E(G_{\mathrm{2}})$ are disjoint as well. The join of $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ is a digraph $G=G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}$ such that

$•$the set of vertices of the digraph $G$ is $V(G_{\mathrm{1}})\bigcup V(G_{\mathrm{2}})$;

$•$ the set of directed edges of the digraph $G$ is

$E(G_{\mathrm{1}})\bigcup E(G_{\mathrm{2}})\bigcup \{(u,v)|u\in V(G_{\mathrm{1}}),v\in V(G_{\mathrm{2}})\}$

2.1 Discrete Morse Functions on the Join of Digraphs

In this subsection, we will give a necessary and sufficient condition that the function on the join determined by the discrete Morse functions on factors is a discrete Morse function.

Firstly, we prove that discrete Morse functions on the join of digraphs have the following important property.

Lemma 4   Let $f$ be a discrete Morse function on $G=G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}$. Then there exists at most one zero-point of $f$ on $G$.

Proof   Suppose to the contrary, there are two distinct vertices $v^{\text{'}},v^{″}\in V(G)$ such that $f(v^{\text{'}})=f(v^{″})=\mathrm{0}$. Then by the definition of join of digraphs, there are three cases to be considered.

Case 1 Both of $v^{\text{'}},v^{″}$ are in $V(G_{\mathrm{1}})$. Then for any allowed elementary path $\alpha =v_{\mathrm{0}}\cdots v_t$ on $G_{\mathrm{2}}$, we have that

${\alpha }^{\text{'}}=v^{\text{'}}{v}_{\mathrm{0}}\cdots v_t$

and

${\alpha }^{″}=v^{″}{v}_{\mathrm{0}}\cdots v_t$

are two distinct allowed elementary $(p+\mathrm{1})$-paths on $G$ such that $f({\alpha }^{\text{'}})=f({\alpha }^{″})=f(\alpha )$. This contradicts that $f$ is a discrete Morse function on $G$.

Case 2 Both of $v^{\text{'}},v^{″}$ are in $V(G_{\mathrm{2}})$. Similar to Case 1, for any allowed elementary path $\alpha =v_{\mathrm{0}}\cdots v_s$ on $G_{\mathrm{1}},$

${\alpha }^{\text{'}}=v_{\mathrm{0}}\cdots v_t{v}^{\text{'}}$

and

${\alpha }^{″}=v_{\mathrm{0}}\cdots v_s{v}^{″}$

are two distinct allowed elementary $(p+\mathrm{1})$-paths on $G$ such that $f({\alpha }^{\text{'}})=f({\alpha }^{″})=f(\alpha )$ which contradicts that $f$ is a discrete Morse function on $G$.

Case 3 $v^{\text{'}}\in V(G_{\mathrm{1}})$ and $v^{″}\in V(G_{\mathrm{2}})$. Then $f(v^{\text{'}}{v}^{″})=f(v^{\text{'}})=f(v^{″})$ . This also contradicts that $f$ is a discrete Morse function on $G$.

Combining Case 1, Case 2 and Case 3, the lemma is proved.

Secondly, define a function $f$

$f(v)=\{\begin{array}{c}{f}_{\mathrm{1}}(v),\begin{array}{cc}& v\in V_{\mathrm{1}}\end{array}\\ f_{\mathrm{2}}(v),\begin{array}{cc}& v\in V_{\mathrm{2}}\end{array}\end{array}$(1)

on $G=G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}$, where $f_{\mathrm{1}}$ and $f_{\mathrm{2}}$ are functions on $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$, respectively. Then by Lemma 4 and (1), we have that

Lemma 5   $f$ is a discrete Morse function on $G=G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}$ if and only if there exist discrete Morse functions $f_{\mathrm{1}}$ on $G_{\mathrm{1}}$ and $f_{\mathrm{2}}$ on $G_{\mathrm{2}}$ respectively such that $f=f_{\mathrm{1}}\mathrm{*}{f}_{\mathrm{2}}$ and one of $f_{\mathrm{1}}$ and $f_{\mathrm{2}}$ is positive while the other one has at most one zero-point.

Proof   ($\Rightarrow )$ Let $f_{\mathrm{1}}={f|}_{G_{\mathrm{1}}}$ and $f_{\mathrm{2}}={f|}_{G_{\mathrm{2}}}$ . Then by (1), $f=f_{\mathrm{1}}\mathrm{*}{f}_{\mathrm{2}}$ and by Definition 1, $f_{\mathrm{1}}$, $f_{\mathrm{2}}$ are discrete Morse functions on $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$, respectively. Moreover, by Lemma 4, one of $f_{\mathrm{1}}$ and $f_{\mathrm{2}}$ is positive and the other one has at most one zero-point.

$(\Leftarrow$) Without loss of generality, $f_{\mathrm{1}}$ is a positive function on $G_{\mathrm{1}}$ and $f_{\mathrm{2}}$ is nonnegative on $G_{\mathrm{2}}$. Let α be an arbitrary allowed elementary n-path on $G$. Then by Ref.[3, Proposition 6.4],

$\alpha ={\alpha }_{\mathrm{1}}\mathrm{*}{\alpha }_{\mathrm{2}}$

where ${\alpha }_{\mathrm{1}}=v_{\mathrm{0}}\cdots v_s\in P(G_{\mathrm{1}})$, ${\alpha }_{\mathrm{2}}=w_{\mathrm{0}}\cdots w_t\in P(G_{\mathrm{2}})$, $s+t+\mathrm{1}=n$. Consider the following cases:

Case 1 $t\ge \mathrm{0}$. Suppose ${\beta }_{\mathrm{1}}$ and ${\beta }_{\mathrm{2}}$ are two allowed elementary paths on $G$ such that ${\beta }_{\mathrm{1}}<\alpha$, ${\beta }_{\mathrm{2}}<\alpha$ and $f({\beta }_{\mathrm{1}})=f({\beta }_{\mathrm{2}})=f(\alpha )$. Since $f_{\mathrm{1}}(v)>\mathrm{0}$ for each $v\in V(G_{\mathrm{1}})$, it follows that $f_{\mathrm{1}}(v_i)>\mathrm{0}$ for $\mathrm{0}\le i\le s$.Then there are two indices $\mathrm{0}\le j\ne k\le t$ such that $f_{\mathrm{2}}(w_j)=f_{\mathrm{2}}(w_k)=\mathrm{0}$. This contradicts Lemma 2. Therefore,

$\#\{{\beta }^{(n-\mathrm{1})}<{\alpha }^{(n)}|f(\beta )=f(\alpha )\}\le \mathrm{1}$

Suppose ${\gamma }_{\mathrm{1}}$ and ${\gamma }_{\mathrm{2}}$ are two allowed elementary paths on $G$ such that ${\gamma }_{\mathrm{1}}>\alpha$, ${\gamma }_{\mathrm{2}}>\alpha$ and $f({\gamma }_{\mathrm{1}})=f({\gamma }_{\mathrm{2}})=f(\alpha )$. Since $f_{\mathrm{1}}(v)>\mathrm{0}$ for each $v\in V(G_{\mathrm{1}})$, it follows that

${\gamma }_{\mathrm{1}}={\alpha }_{\mathrm{1}}\mathrm{*}{\alpha }_{\mathrm{2}}^{\text{'}}$

and

${\gamma }_{\mathrm{2}}={\alpha }_{\mathrm{1}}\mathrm{*}{\alpha }_{\mathrm{2}}^{″}$

where ${\alpha }_{\mathrm{2}}^{\text{'}}=w_{\mathrm{0}}\cdots w_{i}u{w}_{i+\mathrm{1}}\cdots w_t$, ${\alpha }_{\mathrm{2}}^{″}=w_{\mathrm{0}}\cdots w_{j}w{w}_{j+\mathrm{1}}\cdots w_t$ and $f_{\mathrm{2}}(u)=f_{\mathrm{2}}(w)=\mathrm{0}$. Since there exists at most one zero-point of $f_{\mathrm{2}}$, it follows that $u=w$ and $i\ne j$. Without loss of generality, $i<j$. Thus, there exists a directed loop

$w{w}_{i+\mathrm{1}}\cdots w_{j}w$

on $G_{\mathrm{2}}$ with $f_{\mathrm{2}}(w)=\mathrm{0}$. This contradicts Lemma 1. Therefore,

$\#\{{\gamma }^{(n+\mathrm{1})}>{\alpha }^{(n)}|f(\gamma )=f(\alpha )\}\le \mathrm{1}$

Case 2 $t=-\mathrm{1}$. Then for any allowed elementary n-path $\alpha$ on $G$,

$\alpha ={\alpha }_{\mathrm{1}}$

where ${\alpha }_{\mathrm{1}}=v_{\mathrm{0}}\cdots v_n\in P(G_{\mathrm{1}})$. Obviously, since $f_{\mathrm{1}}(v)>\mathrm{0}$ for all vertices $v\in V(G_{\mathrm{1}})$, it follows that $f(\beta )<f(\alpha )$ for any allowed elementary path $\beta <\alpha$. Hence,

$\#\{{\beta }^{(n-\mathrm{1})}<{\alpha }^{(n)}|f(\beta )=f(\alpha )\}=\mathrm{0}$

Moreover, since there exists at most one vertex $w\in P(G_{\mathrm{2}})$ such that $f_{\mathrm{2}}(w)=\mathrm{0}$, it follows that there exists at most one allowed elementary path

$\gamma =v_{\mathrm{0}}\cdots v_{n}w$

such that $\gamma >\alpha$ and $f(\gamma )=f(\alpha )$. Hence,

$\#\{{\gamma }^{(n+\mathrm{1})}>{\alpha }^{(n)}|f(\gamma )=f(\alpha )\}\le \mathrm{1}$

Summarizing Case 1 and Case 2, due to the arbitrariness of $\alpha$, $f$ is a discrete Morse function on $G$.

Therefore, the lemma is proved.

Moreover, we have

Theorem 3^{[18 , Theorem 2.12]} Let $G$ be a digraph and $f:V(G)\to [\mathrm{0},+\mathrm{\infty })$ be a discrete Morse function on $G$. Then $f$ can be extended to be a Morse function $\overline{f}$ on $\overline{G}$ such that $\overline{f}(v)=f(v)$ for each vertex $v\in V(G)$ if and only if the following condition (*) is satisfied.

(*) for each vertex $v\in V(G)$, there exists at most one zero-point of $f$ in all allowed elementary paths starting or ending at $v$.

Therefore, by Lemma 5 and Theorem 3, we have that

Corollary 1   Let $f_{\mathrm{1}}:V(G_{\mathrm{1}})\to (\mathrm{0},+\mathrm{\infty })$ be a function on $G_{\mathrm{1}}$ and $f_{\mathrm{2}}:V(G_{\mathrm{2}})\to [\mathrm{0},+\mathrm{\infty })$ be a discrete Morse function on $G_{\mathrm{2}}$ with at most one zero-point. Then the function $f$ defined in (1) is extendable.

Proof   By Theorem 3, $f_{\mathrm{1}}$ can be extended to be a discrete Morse function ${\overline{f}}_{\mathrm{1}}$ on ${\overline{G}}_{\mathrm{1}}$ such that ${\overline{f}}_{\mathrm{1}}(v)=f_{\mathrm{1}}(v)$ for $v\in V(G_{\mathrm{1}})$, and $f_{\mathrm{2}}$ can be extended to be a discrete Morse function ${\overline{f}}_{\mathrm{2}}$ on ${\overline{G}}_{\mathrm{2}}$ such that ${\overline{f}}_{\mathrm{2}}(w)=f_{\mathrm{2}}(w)$ for $w\in V(G_{\mathrm{2}})$.

By Lemma 5, $f$ is a discrete Morse function on $G$ and $f$ is extendable.

Define a function $\overline{f}:V(\overline{G})\to [\mathrm{0},+\mathrm{\infty })$ such that

$\overline{f}(v)=\{\begin{array}{c}{\overline{f}}_{\mathrm{1}}(v),\begin{array}{cc}& v\in V(G_{\mathrm{1}}),\end{array}\\ {\overline{f}}_{\mathrm{2}}(v),\begin{array}{cc}& v\in V(G_{\mathrm{2}}).\end{array}\end{array}$

Then $\overline{f}$ is the extension of $f$ on $\overline{G}$ such that $\overline{f}(v)=f(v)$ for $v\in V(G)$.

Remark 1   Let $f_{\mathrm{1}},f_{\mathrm{2}}$ be discrete Morse functions on digraphs $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$, respectively. By Lemma 5 and Corollary 1, unless otherwise specified, we always assume that $f_{\mathrm{1}}$ is positive and $f_{\mathrm{2}}$ has at most a unique zero-point in this paper. Denote the extended discrete Morse function of $f$ on $\overline{G}=\stackrel{\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}}$ as $\overline{f}$.

2.2 Transitive Closure of Join of Digraphs, Discrete Gradient Vector Field on the Transitive Closure

Firstly, it is easy to prove that the transitive closure of join of two digraphs are the same as the join of their transitive closures. That is,

Proposition 1   Let $G_{\mathrm{1}}$ and $G_{\mathrm{2}}$ be two digraphs. Then

$\stackrel{\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}}={\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}}$

Proof   Firstly,

$\begin{array}{l}V(\stackrel{\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}})=V(G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})=V(G_{\mathrm{1}})\bigcup V(G_{\mathrm{2}})\\ =V({\overline{G}}_{\mathrm{1}})\bigcup V({\overline{G}}_{\mathrm{2}})\end{array}$

Secondly, we will prove

$E(\stackrel{\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}})=E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})$(2)

and divide the proof into the following two steps.

Step 1   Since $G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}\subseteq {\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}}$, it is sufficient to prove that for each directed edge $(u,w)\in E(\stackrel{\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}})\backslash E(G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})$,$(u,w)\in E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})$. Since for any $(u,w)\in E(\stackrel{\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}})\backslash E(G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})$, there exist a sequence of directed edges $\{v_i{v}_{i+\mathrm{1}}{\}}_{i=\mathrm{0}}^{n-\mathrm{1}}$ such that $v_i{v}_{i+\mathrm{1}}\in E(G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})$ with $v_{\mathrm{0}}=u$ and $v_n=w$. Since $V(G_{\mathrm{1}})\bigcap V(G_{\mathrm{2}})=\mathrm{\varnothing }$, there are three cases to be considered.

Case 1 Each $v_i{v}_{i+\mathrm{1}}\in E(G_{\mathrm{1}})$, $\mathrm{0}\le i\le n-\mathrm{1}$. Then $uw=v_{\mathrm{0}}{v}_n\in E({\overline{G}}_{\mathrm{1}})\subseteq E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})$.

Case 2 Each $v_i{v}_{i+\mathrm{1}}\in E(G_{\mathrm{2}})$,$\mathrm{0}\le i\le n-\mathrm{1}$. Then $uw=v_{\mathrm{0}}{v}_n\in E({\overline{G}}_{\mathrm{2}})\subseteq E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})$.

Case 3 There exists a directed edge $v_k{v}_{k+\mathrm{1}}\in E(G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})\backslash E(G_{\mathrm{1}})\bigcup E(G_{\mathrm{2}})$. Then by the definition of join of digraphs, vertices $v_{\mathrm{0}},v_{\mathrm{1}},\cdots ,v_k$ are all in $G_{\mathrm{1}}$ and $v_{k+\mathrm{1}},\cdots ,v_n$ are all in $G_{\mathrm{2}}$. Thus,

$uw=v_{\mathrm{0}}{v}_n\in E(G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})\backslash E(G_{\mathrm{1}})\bigcup E(G_{\mathrm{2}})\subseteq E(G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})$

Combing Case 1-Case 3, $E(\stackrel{\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}}\backslash G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})\subseteq E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})$. Hence, $E(\stackrel{\_\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}})\subseteq E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})$.

Step 2   By the definition of join of digraphs, we have that

$E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})=E({\overline{G}}_{\mathrm{1}})\bigcup E({\overline{G}}_{\mathrm{2}})\bigcup \{(u,v)|u\in V({\overline{G}}_{\mathrm{1}}),v\in V({\overline{G}}_{\mathrm{2}})\}$

$=E({\overline{G}}_{\mathrm{1}})\bigcup E({\overline{G}}_{\mathrm{2}})\bigcup \{(u,v)|u\in V(G_{\mathrm{1}}),v\in V(G_{\mathrm{2}})\}$

Moreover,

$•E({\overline{G}}_{\mathrm{1}})\subseteq E(\stackrel{\_\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}});$

$•E({\overline{G}}_{\mathrm{2}})\subseteq E(\stackrel{\_\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}});$

$•$ for each $(u,v)\in E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})$ such that $u\in V(G_{\mathrm{1}})$ and $v\in V(G_{\mathrm{2}})$,

$(u,v)\in E(G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}})\subseteq E(\stackrel{\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}}).$

Hence, $E(\stackrel{\_\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}})\supseteq E({\overline{G}}_{\mathrm{1}}\mathrm{*}{\overline{G}}_{\mathrm{2}})$.

Therefore, (2) is proved and the proposition holds.

By Proposition 1 and Ref.[3, Proposition 6.4], we have

Corollary 2   Suppose $\alpha$ is an arbitrary allowed elementary n-path on $\stackrel{\_\_\_\_\_\_\_\_\_}{G_{\mathrm{1}}\mathrm{*}{G}_{\mathrm{2}}}$. Then there exist ${\alpha }_{\mathrm{1}}\in P_s({\overline{G}}_{\mathrm{1}})$ and ${\alpha }_{\mathrm{2}}\in P_t({\overline{G}}_{\mathrm{2}})$ such that $\alpha ={\alpha }_{\mathrm{1}}\mathrm{*}{\alpha }_{\mathrm{2}}$, $s+t+\mathrm{1}=n$ and $s,t\ge -\mathrm{1}$.

For each $n\ge \mathrm{0}$, denote $\mathrm{C}\mathrm{r}\mathrm{i}{\mathrm{t}}_n(G)$ as the free $R$-module consisting of all the formal linear combinations of critical n-paths on digraph $G$.

Lemma 6   Suppose$\alpha \in \mathrm{C}\mathrm{r}\mathrm{i}{\mathrm{t}}_n(\overline{G})$. Then there exist ${\alpha }_{\mathrm{1}}\in \mathrm{C}\mathrm{r}\mathrm{i}{\mathrm{t}}_s({\overline{G}}_{\mathrm{1}})$ and ${\alpha }_{\mathrm{2}}\in \mathrm{C}\mathrm{r}\mathrm{i}{\mathrm{t}}_t({\overline{G}}_{\mathrm{2}})$ such that $\alpha ={\alpha }_{\mathrm{1}}\mathrm{*}{\alpha }_{\mathrm{2}},$$s+t+\mathrm{1}=n$.

Proof   By Corollary 2, $\alpha ={\alpha }_{\mathrm{1}}\mathrm{*}{\alpha }_{\mathrm{2}}$ where ${\alpha }_{\mathrm{1}}\in P_s({\overline{G}}_{\mathrm{1}})$ and ${\alpha }_{\mathrm{2}}\in P_t({\overline{G}}_{\mathrm{2}})$. By Lemma 5, since $f$ is the discrete Morse function on $G$ decided by $f_{\mathrm{1}}$ and $f_{\mathrm{2}}$, it follows that one of $f_{\mathrm{1}}$ and $f_{\mathrm{2}}$ is positive and the other one has at most one zero-point. Without loss of generality, $f_{\mathrm{1}}$ is positive on $V(G_{\mathrm{1}})$ and $f_{\mathrm{2}}$ has at most one zero-point. Then the extension ${\overline{f}}_{\mathrm{1}}$ of $f_{\mathrm{1}}$ is positive on $V({\overline{G}}_{\mathrm{1}})$ and each allowed elementary path on ${\overline{G}}_{\mathrm{1}}$ is critical on ${\overline{G}}_{\mathrm{1}}$. Hence, ${\alpha }_{\mathrm{1}}$ is a critical path on ${\overline{G}}_{\mathrm{1}}$ and the crucial part of the proof is to verify that ${\alpha }_{\mathrm{2}}$ is a critical path on ${\overline{G}}_{\mathrm{2}}$. Consider the following two cases.

Case 1 There exists no zero-point of $f_{\mathrm{2}}$. Obviously, ${\alpha }_{\mathrm{1}}\in \mathrm{C}\mathrm{r}\mathrm{i}{\mathrm{t}}_s({\overline{G}}_{\mathrm{1}})$ and ${\alpha }_{\mathrm{2}}\in \mathrm{C}\mathrm{r}\mathrm{i}{\mathrm{t}}_t({\overline{G}}_{\mathrm{2}})$.