Spanning trees in directed square cycles

Abstract

We classify weakly connected spanning closed (WCSC) subgraphs of $\overrightarrow{C_n^2}$, the square of a directed $n$-vertex cycle. Then we show that every spanning tree of $\overrightarrow{C_n^2}$ is contained in a unique nontrivial WCSC subgraph of $\overrightarrow{C_n^2}$. As a result, we obtain a purely combinatorial derivation of the formula for the number of directed spanning trees of $\overrightarrow{C_n^2}$. Moreover, we obtain the formula for the number of directed spanning trees of $\overrightarrow{C_n^2}$, which is a Jacobsthal number.