Counting oriented spanning trees in generalized join digraphs

Abstract

Let $G$ be a digraph with vertex set $\{1,2,...,n\}$ and $H_1,H_2,...,H_n$ be $n$ digraphs. The generalized join digraph $\overrightarrow{G}=G[H_1,H_2,...,H_n]$ is a digraph obtained from $G$ by replacing each vertex $i$ with $H_i$ and for any $u\in V(H_i)$ and $v\in V(H_j)$, $(u,v)\in E(\overrightarrow{G})$ if and only if $(i,j)\in E(G)$. In this paper we express the number of oriented spanning trees in $\overrightarrow{G}$ in terms of Laplacian eigenvalues of $H_1,H_2,...,H_n$ and oriented spanning trees of $G$. Furthermore, we consider the number of oriented spanning trees with a fixed root in $\overrightarrow{G}$. First, we introduce the biclique-directed star transformation formula for counting oriented spanning trees with a fixed root in digraphs. Using it, we give the formula for the total number of oriented spanning trees with roots in a certain $H_i$ $(1\le i\le n)$ of $\overrightarrow{G}$ in terms of Laplacian eigenvalues of $H_1,H_2,...,H_n$ and oriented spanning trees of $G$. As applications, when each $H_i$ is a given digraph, the enumerative formulas for oriented spanning trees with a fixed root of $\overrightarrow{G}$ are derived from our work.

Topics & keywords