The enumeration of spanning tree of weighted graphs

Abstract

A polynomial associated with G is defined as $t(G,w)=\sum _{T\in {\mathbb {T}}(G)}\prod _{e\in E(T)}w_e(G)$ (${\mathbb {T}}(G)$ is the set of spanning trees of G), which is a weighted enumeration of spanning trees of graphs. It is known that any graph G is an intersection graph of a linear hypergraph, which corresponds to a clique partition of G. In this paper, we introduce the Schur complement formula and local transformation formula of t(G, w). By using these formulas, we obtain some expressions of t(G, w) for weighted intersection graphs and express the number of spanning trees of graph G in terms of clique partitions of G. As applications, expressions for enumerating spanning trees in bipartite graphs, line graphs, generalized line graphs, middle graphs, total graphs, generalized join graphs and vertex-weighted graphs are derived from our work.

1 Introduction

Let G be a weighted graph with vertex set V(G) and edge set E(G), and each edge $e=\{i,j\}\in E(G)$ is weighted by an indeterminate $w_e(G)=w_{ij}(G)=w_{ji}(G)$. The word “weighted” is omitted when $w_e(G)=1$ for each $e\in E(G)$. Let ${\mathbb {T}}(G)$ denote the set of spanning trees of G. A polynomial associated with G is defined as

$$\begin{aligned} t(G,w)=\sum _{T\in {\mathbb {T}}(G)}\prod _{e\in E(T)}w_e(G), \end{aligned}$$

which is also called Kirchhoff polynomial [10] or weighted spanning tree enumerator [26] of G. We assume that $t(G,w)=1$ when $G=K_1$ is an isolated vertex. From the matrix-tree theorem, t(G, w) is equal to any cofactor of the edge-weighted Laplacian. If $w_e(G)=1$ for each $e\in E(G)$, then $t(G,w)=|{\mathbb {T}}(G)|$ is the number of spanning trees of G. Besides the number of spanning trees, there is more enumerative information in t(G, w). For example, setting $w_f(G)=1$ for all edges $f\ne e$, then the coefficient of $w_e$ in t(G, w) is the number of spanning trees containing e.

Example 1.1

Let $C_3$ be the cycle with 3 edges $e_1,e_2$ and $e_3$. Then,

$$\begin{aligned} t(C_3,w)=w_{e_1}(C_3)w_{e_2}(C_3)+w_{e_1}(C_3)w_{e_3}(C_3)+w_{e_2}(C_3)w_{e_3}(C_3). \end{aligned}$$

The problem of counting spanning trees was first investigated by Kirchhoff in the analysis of electric circuits [24]. It is a classic problem in graph theory and has important applications in physics and network. Matrix-tree theorems for edge-weighted graphs and vertex-weighted graphs were given in [7, 9], respectively. Some scholars have investigated the number of spanning trees of regular graphs [2, 27], cartesian type operations [8, 19], graphs with symmetry [34], line graphs [14, 20, 31] and so on.

From the work of Erdös, Goodman and Pósa [16], we know that any graph G is an intersection graph of a linear hypergraph, which corresponds to a clique partition of G (see Observations 2.1 and 2.2 ). Motivated by this fact, this paper introduces the Schur complement formula and local transformation formula of t(G, w) and uses them to investigate the enumeration of spanning trees via intersection representation and clique partition of a graph.

As applications of our work, we derive formulas for the enumeration of spanning trees in bipartite graphs, line graphs, generalized line graphs, middle graphs, total graphs and generalized join graphs. Some results in [14, 19, 20, 31, 32] are special cases of our results.

Another motivation is the enumeration of oriented spanning trees of a vertex-weighted graph. Chung and Langlands [9] gave a matrix-tree theorem of counting oriented spanning trees of a vertex-weighted graph. We can obtain a clique partition formula for counting oriented spanning trees of any vertex-weighted graph.

This paper is organized as follows: In Sect. 2, we give some basic definitions, notations and auxiliary lemmas. In Sect. 3, we introduce the Schur complement formula and local transformation formula of t(G, w). In Sect. 4, formulas of t(G, w) for weighted intersection graphs are given. In Sect. 5, we express the number of spanning trees of any graph G in terms of clique partitions of G. In Sect. 6, by using the results in Sects. 3–5, we give formulas for the enumeration of spanning trees in bipartite graphs, line graphs, generalized line graphs, middle graphs, total graphs and generalized join graphs. We also obtain a formula for enumerating oriented spanning trees of any vertex-weighted graph G via clique partitions of G.

2 Preliminaries

In this section, we give some basic definitions, notations and auxiliary lemmas on intersection graphs, clique partition, matrix-tree theorem and Schur complement.

2.1 Intersection representation and clique partition of graphs

Let V(H) and E(H) denote the vertex set and the edge set of a hypergraph H, respectively. Every $e\in E(H)$ is a subset of V(H). If $|e|=2$ for each $e\in E(H)$, then H is an ordinary graph. We say that H is linear if $|e_1\cap e_2|\le 1$ for any two $e_1,e_2\in E(H)$. The intersection graph [16] $\Omega (H)$ of H has vertex set E(H), and two vertices $e_1,e_2$ of $\Omega (H)$ are adjacent if and only if $e_1\cap e_2\ne \emptyset$. If a graph G and a (linear) hypergraph H satisfy $G=\Omega (H)$, then H is called an (a linear) intersection representation of G.

A clique in a graph G is a vertex subset $Q\subseteq V(G)$ such that the subgraph induced by Q is complete. An clique covering [17] of G is a set $\varepsilon =\{Q_1,\ldots ,Q_r\}$ of cliques in G that cover all edges of G, that is, each edge of G belongs to at least one $Q_i$. We say that $\varepsilon$ is a clique partition [17] if each edge of G belongs to exactly one clique of $\varepsilon$, that is, any two cliques in $\varepsilon$ have at most one common vertex.

It is known that any graph G has a clique partition (see Theorem 4 in [16]). As shown in the following observations of Erdös et al., there is a one to one correspondence between clique partitions and linear intersection representations of a connected graph G.

Observation 2.1

[16] Let $\varepsilon =\{Q_1,\ldots ,Q_r\}$ be a clique covering of a connected graph G. For a vertex $u\in V(G)$, let $S_u=\{Q_i:u\in Q_i\}$ denote the set of cliques containing u. Let $H_\varepsilon$ be the hypergraph with vertex set $\varepsilon =\{Q_1,\ldots ,Q_r\}$ and edge set $\{S_u:u\in V(G)\}$. Then $G=\Omega (H_\varepsilon )$. If $\varepsilon$ is a clique partition of G, then $H_\varepsilon$ is linear.

Observation 2.2

[16] If a hypergraph H is an intersection representation of graph G, then the set of edges incident to a given vertex of H correspond to a clique of G, and all such cliques form a clique covering of G. When H is linear, this clique covering is a clique partition of G.

Fig. 1

Graph G

The following is an example of the clique partition and intersection representation of graphs.

Example 2.3

The graph G in Fig. 1 has a clique partition $\varepsilon =\{Q_1,Q_2,Q_3\}$, where $Q_1=\{1,2,3\},Q_2=\{2,4,5\},Q_3=\{3,5,6\}$. Let $S_i=\{Q_j:i\in Q_j\}$ denote the set of cliques containing vertex i. Then $S_1=\{Q_1\}$, $S_2=\{Q_1,Q_2\}$, $S_3=\{Q_1,Q_3\}$, $S_4=\{Q_2\}$, $S_5=\{Q_2,Q_3\}$, $S_6=\{Q_3\}$. From Observation 2.1, we know that the linear hypergraph with vertex set $\{Q_1,Q_2,Q_3\}$ and edge set $\{S_1,\ldots ,S_6\}$ is an intersection representation of G.

2.2 Laplacian for edge-weighted graphs

Let G be a weighted graph on n vertices, and each edge $e\in E(G)$ is weighted by an indeterminate $w_e(G)$. For any two vertices $i,j\in V(G)$, we define $w_{ij}(G)$ as

$$\begin{aligned} w_{ij}(G)={\left\{ \begin{array}{ll}w_e(G)\qquad \qquad &{}\text{ if }~\{i,j\}=e\in E(G),\\ 0\qquad \qquad ~~~~~~~&{}\text{ if }~\{i,j\}\notin E(G).\end{array}\right. } \end{aligned}$$

The weighted degree of a vertex i is $d_i(G)=\sum _{j\in V(G)}w_{ij}(G)$. The edge-weighted Laplacian $L_G$ is the $n\times n$ symmetric matrix with entries

$$\begin{aligned} (L_G)_{ij}={\left\{ \begin{array}{ll}d_i(G)\qquad \qquad &{}\text{ if }~i=j,\\ -w_{ij}(G)\qquad \qquad &{}\text{ if }~i\ne j.\end{array}\right. } \end{aligned}$$

A polynomial associated with G is defined as

$$\begin{aligned} t(G,w)=\sum _{T\in {\mathbb {T}}(G)}\prod _{e\in E(T)}w_e(G), \end{aligned}$$

where ${\mathbb {T}}(G)$ denotes the set of spanning trees of G. Let A(i, j) denote the submatrix of a matrix A obtained by deleting the ith row and the jth column. The following is the matrix-tree theorem, which expresses t(G, w) via the determinant of $L_G(i,j)$.

Lemma 2.4

[15] Let G be a weighted graph on n vertices.

• (1) For any $i,j\in \{1,\ldots ,n\}$, we have

  $$\begin{aligned} t(G,w)=(-1)^{i+j}\det (L_G(i,j)). \end{aligned}$$

• (2) If the eigenvalues of $L_G$ are $\mu _1,\ldots ,\mu _{n-1},\mu _n=0$, then

  $$\begin{aligned} t(G,w)=\frac{1}{n}\prod _{i=1}^{n-1}\mu _i. \end{aligned}$$

For a graph G on n vertices, let $\mu _1(G)\ge \cdots \ge \mu _{n-1}(G)\ge \mu _n(G)=0$ denote eigenvalues of $L_G$. Let $\text{ j}_n$ and $J_n$ denote the all-ones column vector of dimension n and the all-ones matrix of order n, respectively. We use I to denote the identity matrix.

Lemma 2.5

Let G be a graph on n vertices. Then,

$$\begin{aligned} \det (L_G+\alpha I+\beta J_n)=(\alpha +n\beta )\prod _{i=1}^{n-1}(\mu _i(G)+\alpha ). \end{aligned}$$

If $\det (L_G+\alpha I+\beta J_n)\ne 0$, then

$$\begin{aligned} \text{ j}_n^\top (L_G+\alpha I+\beta J_n)^{-1}\text{ j}_n=\frac{n}{\alpha +n\beta }. \end{aligned}$$

Proof

The eigenvalues of $L_G+\alpha I+\beta J_n$ are $\mu _1(G)+\alpha ,\ldots ,\mu _{n-1}(G)+\alpha ,\alpha +n\beta$. So $\det (L_G+\alpha I+\beta J_n)=(\alpha +n\beta )\prod _{i=1}^{n-1}(\mu _i(G)+\alpha )$. Since $(L_G+\alpha I+\beta J_n)\text{ j}_n=(\alpha +n\beta )\text{ j}_n$, we have $\text{ j}_n^\top (L_G+\alpha I+\beta J_n)^{-1}\text{ j}_n=\frac{n}{\alpha +n\beta }$ when $\det (L_G+\alpha I+\beta J_n)\ne 0$.

$\square$

2.3 Schur complements in a block matrix

For a block matrix $M=\begin{pmatrix} A&{}B\\ C&{}D\end{pmatrix}$, if A and D are nonsingular, then $D-CA^{-1}B$ and $A-BD^{-1}C$ are called the Schur complements of A and D in M, respectively.

For a matrix E, let $E[i_1,\ldots ,i_s|j_1,\ldots ,j_t]$ denote an $s\times t$ submatrix of E whose row indices and column indices are $i_1,\ldots ,i_s$ and $j_1,\ldots ,j_t$, respectively. The following is a determinant identity involving the Schur complement.

Lemma 2.6

[5] Let $M=\begin{pmatrix}A&{}B\\ C&{}D\end{pmatrix}$ be a block matrix of order n, where $A=M[1,\ldots ,k|1,\ldots ,k]$ is nonsingular. If $k+1\le i_1<\cdots <i_s\le n$ and $k+1\le j_1<\cdots <j_s\le n$, then

$$\begin{aligned} \frac{\det (M[1,\ldots ,k,i_1,\ldots ,i_s|1,\ldots ,k,j_1,\ldots ,j_s])}{\det (A)}=\det (S[i_1,\ldots ,i_s|j_1,\ldots ,j_s]), \end{aligned}$$

where $S=D-CA^{-1}B$.

3 Schur complement and local transformation formulas

This section introduces Schur complement and local transformation formulas for enumerating spanning trees.

3.1 Schur complement formulas for enumerating spanning trees

Let G be a weighted graph with a partition $V(G)=V_1\cup V_2$, and let $L_G=\begin{pmatrix} L_1&{}B\\ B^\top &{}L_2\end{pmatrix}$, where $B^\top$ denotes the transpose of the matrix B and $L_1$ and $L_2$ are principal submatrices of $L_G$ corresponding to $V_1$ and $V_2$, respectively. If $L_1$ and $L_2$ are nonsingular, then the Schur complements in $L_G$ are $S_1=L_1-BL_2^{-1}B^\top$ and $S_2=L_2-B^\top L_1^{-1}B$.

It is known [11, 18, 21] that $S_1$ and $S_2$ are both Laplacian matrices of some weighted graphs (because $S_1$ and $S_2$ are symmetric matrices whose all row sums are zero). We defined the weighted graph with Laplacain matrix $S_k$ as the Schur complement weighted graph of G with respect to $V_k$, denoted by $G(V_k)$ ($k=1,2$). Then, $G(V_k)$ has vertex set $V_k$ and edge set $\{\{u,v\}:(S_k)_{uv}\ne 0,u\ne v\}$.

The Schur complement formula of t(G, w) for a weighted graph G is introduced as follows:

Proposition 3.1

Let G be a weighted graph with a partition $V(G)=V_1\cup V_2$, and let $L_1$ and $L_2$ be principal submatrices of $L_G$ corresponding to $V_1$ and $V_2$, respectively.

• (1) If $L_1$ is nonsingular, then

  $$\begin{aligned} t(G,w)=\det (L_1)t(G(V_2),w). \end{aligned}$$

• (2) If $L_2$ is nonsingular, then

  $$\begin{aligned} t(G,w)=\det (L_2)t(G(V_1),w). \end{aligned}$$

Proof

The Laplacian matrix of G can be written as $L_G=\begin{pmatrix}L_1&{}B\\ B^\top &{}L_2\end{pmatrix}$. The Schur complement $L_2-B^\top L_1^{-1}B=L_{G(V_2)}$ is the Laplacian matrix of the Schur complement weighted graph $G(V_2)$. By Lemmas 2.4 and 2.6 , we have

$$\begin{aligned} t(G,w)=\det (L_1)\det (L_{G(V_2)}(i,i))=\det (L_1)t(G(V_2),w), \end{aligned}$$

where $L_{G(V_2)}(i,i)$ is the submatrix of $L_{G(V_2)}$ obtained by deleting the ith row and the ith column ($i\in V_2$).

Note that $L_G$ can be also written as $L_G=\begin{pmatrix}L_2&{}B^\top \\ B&{}L_1\end{pmatrix}$. Similar to the above proof, we can also get $t(G,w)=\det (L_2)t(G(V_1),w)$. $\square$

The following is an example of Schur complement weighted graphs.

Example 3.2

Let $P_5$ be the path with vertex set $\{1,2,3,4,5\}$, and its edges are weighted by indeterminates $w_{12},w_{23},w_{34}$ and $w_{45}$. Let $V_1=\{1,2,4\},V_2=\{3,5\}$, then the Laplacian matrix of $P_5$ can be partitioned as $L_{P_5}=\begin{pmatrix}L_1&{}B\\ B^\top &{}L_2\end{pmatrix}$, where $B=\begin{pmatrix}0&{}0\\ -w_{23}&{}0\\ -w_{34}&{}-w_{45}\end{pmatrix}$, $L_1=\begin{pmatrix} w_{12}&{}-w_{12}&{}0\\ -w_{12}&{}w_{12}+w_{23}&{}0\\ 0&{}0&{}w_{34}+w_{45}\end{pmatrix}$ and $L_2=\begin{pmatrix} w_{23}+w_{34}&{}0\\ 0&{}w_{45}\end{pmatrix}$ are principal submatrices of $L_{P_5}$ corresponding to $V_1$ and $V_2$, respectively. By computation, the Schur complements $L_{G(V_1)}=S_1=L_1-BL_2^{-1}B^\top$ and $L_{G(V_2)}=S_2=L_2-B^\top L_1^{-1}B$ are

$$\begin{aligned} L_{G(V_1)}= & {} \begin{pmatrix}w_{12}&{}-w_{12}&{}0\\ -w_{12}&{}w_{12}+w_{23}w_{34}(w_{23}+w_{34})^{-1}&{}-w_{23}w_{34}(w_{23} +w_{34})^{-1}\\ 0&{}-w_{23}w_{34}(w_{23}+w_{34})^{-1}&{}w_{23}w_{34}(w_{23}+w_{34})^{-1} \end{pmatrix},\\ L_{G(V_2)}= & {} \begin{pmatrix}w_{34}w_{45}(w_{34}+w_{45})^{-1} &{}-w_{34}w_{45}(w_{34}+w_{45})^{-1}\\ -w_{34}w_{45}(w_{34}+w_{45})^{-1} &{}w_{34}w_{45}(w_{34}+w_{45})^{-1}\end{pmatrix}. \end{aligned}$$

Hence, the Schur complement weighted graph $G(V_1)$ is the path $P_3$ with edge weights $w_{12}$ and $w_{23}w_{34}(w_{23}+w_{34})^{-1}$, the Schur complement weighted graph $G(V_2)$ is the path $P_2$ with edge weight $w_{34}w_{45}(w_{34}+w_{45})^{-1}$, and

$$\begin{aligned} t(G(V_1),w)=w_{12}w_{23}w_{34}(w_{23}+w_{34})^{-1},~t(G(V_2),w)=w_{34}w_{45}(w_{34}+w_{45})^{-1}. \end{aligned}$$

By Proposition 3.1, we have

$$\begin{aligned} t(P_5,w)= & {} \det (L_1)t(G(V_2),w)=w_{12}w_{23}(w_{34}+w_{45})\frac{w_{34}w_{45}}{w_{34}+w_{45}}\\= & {} w_{12}w_{23}w_{34}w_{45},\\ t(P_5,w)= & {} \det (L_2)t(G(V_1),w)=(w_{23}+w_{34})w_{45}\frac{w_{12}w_{23}w_{34}}{w_{23}+w_{34}}\\= & {} w_{12}w_{23}w_{34}w_{45}. \end{aligned}$$

If G is a connected weighted graph with positive weights, then every proper principal submatrix of $L_G$ is positive definite. So the following consequence is derived from Proposition 3.1.

Proposition 3.3

Let G be a connected weighted graph with positive weights. For any partition $V(G)=V_1\cup V_2$ ($V_1,V_2\ne \emptyset$), we have

$$\begin{aligned} t(G,w)=\det (L_1)t(G(V_2),w)=\det (L_2)t(G(V_1),w), \end{aligned}$$

where $L_1$ and $L_2$ are principal submatrices of $L_G$ corresponding to $V_1$ and $V_2$, respectively.

For $u\in V(G)$, let $N_G(u)$ denote the set of neighbors of u in G. By using the Schur complement formula in Proposition 3.1, we obtain the following expression of t(G, w) for a bipartite weighted graph G.

Theorem 3.4

Let G be a connected bipartite weighted graph with a bipartition $V(G)=V_1\cup V_2$. Then,

$$\begin{aligned} t(G,w)= & {} \prod _{i\in V_1}d_i(G)\sum _{T\in {\mathbb {T}}(G(V_2))}\prod _{\{u,v\}\in E(T)}\left( \sum _{i\in N_G(u)\cap N_G(v)}\frac{w_{ui}(G)w_{vi}(G)}{d_i(G)}\right) \\= & {} \prod _{i\in V_2}d_i(G)\sum _{T\in {\mathbb {T}}(G(V_1))}\prod _{\{u,v\}\in E(T)}\left( \sum _{i\in N_G(u)\cap N_G(v)}\frac{w_{ui}(G)w_{vi}(G)}{d_i(G)}\right) , \end{aligned}$$

where $G(V_k)$ has edge set

$$\begin{aligned} \{\{u,v\}:u\ne v,u,v\in V_k,N_G(u)\cap N_G(v)\ne \emptyset \}~(k=1,2). \end{aligned}$$

Proof

The Laplacian matrix of G can be partitioned as $L_G=\begin{pmatrix}L_1&{}B\\ B^\top &{}L_2\end{pmatrix}$, where $L_1$ and $L_2$ are diagonal matrices of weighted vertex degrees corresponding to $V_1$ and $V_2$, respectively. From Proposition 3.1, we have

$$\begin{aligned} t(G,w)=\det (L_1)t(G(V_2),w)=t(G(V_2),w)\prod _{i\in V_1}d_i(G). \end{aligned}$$

(3.1)

The Laplacian matrix of $G(V_2)$ is the Schur complement $L_{G(V_2)}=L_2-B^\top L_1^{-1}B$. For two vertices $u,v\in V_2$, u and v are adjacent in $G(V_2)$ if and only if $(L_2-B^\top L_1^{-1}B)_{uv}\ne 0$, that is, $N_G(u)\cap N_G(v)\ne \emptyset$. If u and v are adjacent in $G(V_2)$, then the weight of the edge $\{u,v\}$ in $G(V_2)$ is

$$\begin{aligned} w_{uv}(G(V_2))=\Big (B^\top L_1^{-1}B\Big )_{uv}=\sum _{i\in N_G(u)\cap N_G(v)}\frac{w_{ui}(G)w_{vi}(G)}{d_i(G)}. \end{aligned}$$

Hence,

$$\begin{aligned} t(G(V_2),w)= & {} \sum _{T\in {\mathbb {T}}(G(V_2))}\prod _{\{u,v\}\in E(T)}w_{uv}(G(V_2))\\= & {} \sum _{T\in {\mathbb {T}}(G(V_2))}\prod _{\{u,v\}\in E(T)}\left( \sum _{i\in N_G(u)\cap N_G(v)}\frac{w_{ui}(G)w_{vi}(G)}{d_i(G)}\right) . \end{aligned}$$

By Eq. (3.1), we have

$$\begin{aligned} t(G,w)= & {} t(G(V_2),w)\prod _{i\in V_1}d_i(G)\\= & {} \prod _{i\in V_1}d_i(G)\sum _{T\in {\mathbb {T}}(G(V_2))}\prod _{\{u,v\}\in E(T)}\left( \sum _{i\in N_G(u)\cap N_G(v)}\frac{w_{ui}(G)w_{vi}(G)}{d_i(G)}\right) . \end{aligned}$$

Similar to the above proof, we can also get

$$\begin{aligned} t(G,w)=\prod _{i\in V_2}d_i(G)\sum _{T\in {\mathbb {T}}(G(V_1))}\prod _{\{u,v\}\in E(T)}\left( \sum _{i\in N_G(u)\cap N_G(v)}\frac{w_{ui}(G)w_{vi}(G)}{d_i(G)}\right) . \end{aligned}$$

$\square$

3.2 Local transformation formulas for enumerating spanning trees

By using the Schur complement formula in Proposition 3.1, we can obtain the following local transformation formula for t(G, w).

Theorem 3.5

Let G be a weighted graph. For a vertex set $U\subseteq V(G)$, let $G_U$ be the weighted graph obtained from G by adding a new vertex v such that $w_{ij}(G_U)$ satisfies

$$\begin{aligned} w_{ij}(G_U)={\left\{ \begin{array}{ll}w_j(G)\sum _{u\in U}w_u(G)\qquad \qquad &{}\text{ if }~i=v,j\in U,\\ 0\qquad \qquad \qquad \qquad \qquad \qquad &{}\text{ if }~i=v,j\in V(G)\backslash U,\\ w_{ij}(G)-w_i(G)w_j(G)\qquad \qquad &{}\text{ if }~\{i,j\}\subseteq U,\\ w_{ij}(G)\qquad \qquad \qquad \qquad &{}\text{ otherwise },\end{array}\right. } \end{aligned}$$

where $\{w_i(G)\}_{i\in U}$ are indeterminates on U. Then,

$$\begin{aligned} t(G_U,w)=\left( \sum _{u\in U}w_u(G)\right) ^2t(G,w). \end{aligned}$$

Proof

The Laplacian matrix of $G_U$ can be written as $L_{G_U}=\begin{pmatrix}d_v(G_U)&{}x^\top \\ x&{}L_2\end{pmatrix}$, where $L_2$ is the principal submatrix of $L_{G_U}$ corresponding to V(G). For two vertices $i,j\in V(G)$, by the definition of $w_{ij}(G_U)$, we have

$$\begin{aligned} (L_2)_{ij}={\left\{ \begin{array}{ll} -w_{ij}(G)+w_i(G)w_j(G)\qquad \qquad &{}\text{ if }~\{i,j\}\subseteq U,\\ -w_{ij}(G)\qquad \qquad \qquad \qquad \qquad \qquad &{}\text{ otherwise },\end{array}\right. } \end{aligned}$$

and the weighted degree of v is

$$\begin{aligned} d_v(G_U)=\sum _{j\in U}w_{vj}(G_U)=\left( \sum _{u\in U}w_u(G)\right) ^2. \end{aligned}$$

The Schur complement weighted graph $G_U(V(G))$ has Laplacian matrix $L_{G_U(V(G))}=L_2-d_v(G_U)^{-1}xx^\top$. Note that $(x)_j=-w_j(G)\sum _{u\in U}w_u(G)$ if $j\in U$, and $(x)_j=0$ if $j\in V(G)\backslash U$. For any two vertices $i,j\in V(G)$, we have

$$\begin{aligned} (xx^\top )_{ij}={\left\{ \begin{array}{ll} \left( \sum _{u\in U}w_u(G)\right) ^2w_i(G)w_j(G)\qquad \qquad ~\text{ if }~\{i,j\}\subseteq U,\\ 0\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad ~~~~~~\text{ otherwise },\end{array}\right. } \end{aligned}$$

and

$$\begin{aligned} (L_2-d_v(G_U)^{-1}xx^\top )_{ij}=-w_{ij}(G). \end{aligned}$$

Hence, $L_{G_U(V(G))}=L_G$, that is, $G_U(V(G))$ and G are isomorphic weighted graphs. By Proposition 3.1, we have

$$\begin{aligned} t(G_U,w)=d_v(G_U)t(G_U(V(G)),w)=\left( \sum _{u\in U}w_u(G)\right) ^2t(G,w). \end{aligned}$$

$\square$

The following corollary is obtained when $w_i(G)=1$ for each $i\in U$ in Theorem 3.5.

Corollary 3.6

Let G be a weighted graph. For a vertex set $U\subseteq V(G)$, let $G_U$ be the weighted graph obtained from G by adding a new vertex v such that $w_{ij}(G_U)$ satisfies

$$\begin{aligned} w_{ij}(G_U)={\left\{ \begin{array}{ll}|U|\qquad \qquad \qquad \qquad ~&{}\text{ if }~i=v,j\in U,\\ 0\qquad \qquad \qquad \qquad ~~~&{}\text{ if }~i=v,j\in V(G)\backslash U,\\ w_{ij}(G)-1\qquad \qquad ~~&{}\text{ if }~\{i,j\}\subseteq U,\\ w_{ij}(G)\qquad \qquad ~~~~~~~&{}\text{ otherwise }.\end{array}\right. } \end{aligned}$$

Then,

$$\begin{aligned} t(G_U,w)=|U|^2t(G,w). \end{aligned}$$

In Corollary 3.6, if U is a clique and $w_{ij}(G)=1$ for any $\{i,j\}\subseteq U$, then we obtain the following mesh-star transformation [20, 30] on t(G, w).

Corollary 3.7

[20, 30] Let G be a weighted graph and $K_c$ be a complete subgraph of G with weight 1 on every edge. If H is obtained from G by replacing $K_c$ by a star $K_{1,c}$ with weight c on every edge, then

$$\begin{aligned} t(H,w)=c^2t(G,w). \end{aligned}$$

Let $\{w_i(G)\}_{i\in V(G)}$ be indeterminates on V(G). If each edge $\{u,v\}$ in G has weight $w_{uv}(G)=w_u(G)w_v(G)$, then we say that G is a weighted graph induced by its vertex weights or the weights of G are induced by $\{w_i(G)\}_{i\in V(G)}$.

The join $G_1\vee G_2$ of two graphs $G_1$ and $G_2$ has vertex set $V(G_1)\cup V(G_2)$ and edge set $E(G_1)\cup E(G_2)\cup \{\{i,j\}:i\in V(G_1),j\in V(G_2)\}$. Let ${\overline{G}}$ denote the complement graph of G, then the join graph $K_1\vee {\overline{G}}$ is the graph obtained from ${\overline{G}}$ by adding a new vertex and joining the new vertex to each vertex of ${\overline{G}}$. We can obtain the following property on local complement transformation from Theorem 3.5.

Corollary 3.8

Let G be a weighted graph whose weights are induced by indeterminates $\{w_i(G)\}_{i\in V(G)}$, and $G_0$ is an induced subgraph of G. Let H be the weighted graph obtained from G by replacing $G_0$ with $K_1\vee \overline{G_0}$, and the weight of an edge $\{i,j\}$ in H is defined as

$$\begin{aligned} w_{ij}(H)={\left\{ \begin{array}{ll}w_j(G)\sum _{u\in V(G_0)}w_u(G)\qquad \qquad ~~~~&{}\text{ if }~i\notin V(G),j\in V(G_0),\\ -w_i(G)w_j(G)\qquad \qquad \qquad \qquad ~~~~&{}\text{ if }~\{i,j\}\in E(\overline{G_0}),\\ w_i(G)w_j(G)\qquad \qquad \qquad \qquad ~~~~~~&{}\text{ if }~\{i,j\}\in E(G)\backslash E(G_0).\end{array}\right. } \end{aligned}$$

Then,

$$\begin{aligned} t(H,w)=\left( \sum _{u\in V(G_0)}w_u(G)\right) ^2t(G,w). \end{aligned}$$

The local complement transformation in Corollary 3.8 yields the following complement transformation formula.

Corollary 3.9

Let G be a weighted graph whose weights are induced by indeterminates $\{w_i(G)\}_{i\in V(G)}$, and let $H=K_1\vee {\overline{G}}$ be the weighted graph induced by indeterminates $\{w_i(H)\}_{i\in V(H)}$, where $w_i(H)=w_i(G)$ if $i\in V(G)$, $w_i(H)=-\sum _{u\in V(G)}w_u(G)$ if $i\notin V(G)$. Then

$$\begin{aligned} t(H,w)=(-1)^{|V(G)|}\left( \sum _{u\in V(G)}w_u(G)\right) ^2t(G,w). \end{aligned}$$

Proof

In Corollary 3.8, when the induced subgraph $G_0=G$, we get a weighted graph $H_0=K_1\vee {\overline{G}}$ such that $t(H_0,w)=\left( \sum _{u\in V(G)}w_u(G)\right) ^2t(G,w)$, and the weight of an edge $\{i,j\}$ in $H_0$ is defined as

$$\begin{aligned} w_{ij}(H_0)={\left\{ \begin{array}{ll}w_j(G)\sum _{u\in V(G)}w_u(G)\qquad \qquad ~~~~&{}\text{ if }~i\notin V(G),j\in V(G),\\ -w_i(G)w_j(G)\qquad \qquad \qquad \qquad ~~~~&{}\text{ if }~\{i,j\}\in E({\overline{G}}).\end{array}\right. } \end{aligned}$$

Since $w_{ij}(H)=-w_{ij}(H_0)$ for all edge $\{i,j\}$, we have

$$\begin{aligned} t(H,w)=(-1)^{|V(G)|}t(H_0,w)=(-1)^{|V(G)|}\left( \sum _{u\in V(G)}w_u(G)\right) ^2t(G,w). \end{aligned}$$

$\square$

The well-known Cayley’s formula tells us that the complete graph $K_n$ has $n^{n-2}$ spanning trees. The Cayley–Prüfer theorem [26] is a generalization of Cayley’s formula. This theorem can be derived from Corollary 3.9 as follows:

Example 3.10

(The Cayley–Prüfer theorem) Let $K_n$ be the weighted complete graph induced by indeterminates $\{w_1,\ldots ,w_n\}$. Then,

$$\begin{aligned} t(K_n,w)=w_1\cdots w_n(w_1+\cdots +w_n)^{n-2}. \end{aligned}$$

Proof

By Corollary 3.9, we have

$$\begin{aligned} t(K_n,w)=(-1)^n\left( \sum _{i=1}^nw_i\right) ^{-2}t(K_{1,n},w)=w_1\cdots w_n(w_1+\cdots +w_n)^{n-2}, \end{aligned}$$

where $K_{1,n}$ is a star with edge weights $-w_j\sum _{i=1}^nw_i$ ($j=1,\ldots ,n$). $\square$

By considering the involution in a graph, Zhang and Yan [34] gave a new proof of the formula for the number of spanning trees in an almost-complete graph. By using Corollary 3.9, we extend this formula as follows:

Example 3.11

Let G be an almost-complete graph obtained from $K_n$ by deleting a matching M of size q, and the weights of G are induced by indeterminates $\{w_1,\ldots ,w_n\}$. Then,

$$\begin{aligned} t(G,w)=\left( \sum _{i=1}^nw_i\right) ^{n-q-2}\left( \prod _{i=1}^nw_i\right) \prod _{\{i,j\}\in M}\sum _{k\ne i,j}w_k. \end{aligned}$$

If $w_1=\cdots =w_n=1$, then we get the formula (4.2) in [34] as follows:

$$\begin{aligned} |{\mathbb {T}}(G)|=n^{n-q-2}(n-2)^q=n^{n-2}\left( 1-\frac{2}{n}\right) ^q. \end{aligned}$$

Proof

Let $H=K_1\vee {\overline{G}}$ be the weighted graph induced by indeterminates $\{w_0,w_1,\ldots ,w_n\}$, where $w_0=-\sum _{i=1}^nw_i$. By Corollary 3.9, we have

$$\begin{aligned} t(G,w)=(-1)^n\left( \sum _{i=1}^nw_i\right) ^{-2}t(H,w). \end{aligned}$$

(3.2)

By computation, we have

$$\begin{aligned} t(H,w)=\left( -\sum _{i=1}^nw_i\right) ^{n-q}\left( \prod _{i=1}^nw_i\right) \prod _{\{i,j\}\in M}\left( -\sum _{k\ne i,j}w_k\right) , \end{aligned}$$

By Eq. (3.2), we get

$$\begin{aligned} t(G,w)=\left( \sum _{i=1}^nw_i\right) ^{n-q-2}\left( \prod _{i=1}^nw_i\right) \prod _{\{i,j\}\in M}\sum _{k\ne i,j}w_k. \end{aligned}$$

$\square$

4 Spanning trees of intersection graphs

The 2-section graph [1] $H_{(2)}$ of a hypergraph H is the graph on the vertex set V(H), and $\{u,v\}\in E(H_{(2)})$ if and only if there exists $e\in E(H)$ such that $\{u,v\}\subseteq e$. The incidence graph $I_H$ is a bipartite graph whose bipartition is $V(I_H)=V(H)\cup E(H)$. For any $u\in V(H)$ and $e\in E(H)$, u and e are adjacent in $I_H$ if and only if u is incident to e in H.

Example 4.1

Let H be a hypergraph with vertex set $V(H)=\{1,2,3,4\}$ and edge set $E(H)=\{e,f\}$, where $e=\{1,2,3\}$, $f=\{2,3,4\}$. Then, the vertex sets and edge sets of the intersection graph $\Omega (H)$, 2-section graph $H_{(2)}$ and incidence graph $I_H$ are listed as follows:

$$\begin{aligned}&V(\Omega (H))=\{e,f\},~E(\Omega (H))=\{\{e,f\}\},\\&V(H_{(2)})=\{1,2,3,4\},~E(H_{(2)})=\{\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{3,4\}\},\\&V(I_H)=\{1,2,3,4,e,f\},~E(I_H)=\{\{1,e\},\{2,e\},\{3,e\},\{2,f\},\{3,f\},\{4,f\}\}. \end{aligned}$$

By using Theorem 3.4, we first give the following relations among spanning trees of $I_H$, $H_{(2)}$ and $\Omega (H)$.

Theorem 4.2

Let H be a connected hypergraph. For $u\in V(H)$ and $e\in E(H)$ incident to u, the edge $\{u,e\}$ in $I_H$ is weighted by an indeterminate $w_{ue}$. Then,

$$\begin{aligned} t(I_H,w)= & {} \prod _{i\in V(H)}\alpha _i\sum _{T\in {\mathbb {T}}(\Omega (H))}\prod _{\{e,f\}\in E(T)}\left( \sum _{u\in e\cap f}\frac{w_{ue}w_{uf}}{\alpha _u}\right) \\= & {} \prod _{e\in E(H)}\alpha _e\sum _{T\in {\mathbb {T}}(H_{(2)})}\prod _{\{u,v\}\in E(T)}\left( \sum _{\{u,v\}\subseteq e\in E(H)}\frac{w_{ue}w_{ve}}{\alpha _e}\right) , \end{aligned}$$

where

$$\begin{aligned} \alpha _i=\sum _{i\in f\in E(H)}w_{if}~(i\in V(H)),~\alpha _e=\sum _{i\in V(H),i\in e}w_{ie}~(e\in E(H)). \end{aligned}$$

Proof

For $i\in V(H)$ and $e\in E(H)$, their weighted degrees in $I_H$ are

$$\begin{aligned} \alpha _i=\sum _{i\in f\in E(H)}w_{if},~\alpha _e=\sum _{i\in V(H),i\in e}w_{ie}. \end{aligned}$$

Note that $V(I_H)=V(H)\cup E(H)$ is the bipartition of the bipartite graph $I_H$. By Theorem 3.4, the edge sets of the Schur complement weighted graphs $I_H(E(H))$ and $I_H(V(H))$ are

$$\begin{aligned}&\{\{e,f\}:e,f\in E(H),e\cap f\ne \emptyset \},\\&\{\{u,v\}:u,v\in V(H),\{u,v\}\in E(H_{(2)})\}. \end{aligned}$$

So the underlying graphs of $I_H(E(H))$ and $I_H(V(H))$ are isomorphic to $\Omega (H)$ and $H_{(2)}$, respectively. Take $G=I_H,V_1=V(H),V_2=E(H)$ in Theorem 3.4, then we can obtain the expression of $t(I_H,w)$. $\square$

The following expression for enumerating spanning trees in $\Omega (H)$ is obtained when $w_{ue}=d_uw_e$ ($d_u=\sum _{u\in e\in E(H)}w_e$) in Theorem 4.2.

Theorem 4.3

Let H be a connected hypergraph. For two edges $e,f\in E(H)$ satisfying $e\cap f\ne \emptyset$, the edge $\{e,f\}$ in $\Omega (H)$ is weighted by $|e\cap f|w_ew_f$, where $\{w_e\}_{e\in E(H)}$ are indeterminates on E(H). Then,

$$\begin{aligned} t(\Omega (H),w)=\frac{\prod _{e\in E(H)}\big (w_e\sum _{u\in e}d_u\big )}{\prod _{u\in V(H)}d_u^2}\sum _{T\in {\mathbb {T}}(H_{(2)})}\prod _{\{u,v\}\in E(T)}\left( \sum _{\{u,v\}\subseteq e\in E(H)}\frac{d_ud_vw_e}{\sum _{i\in e}d_i}\right) , \end{aligned}$$

where $d_u=\sum _{u\in e\in E(H)}w_e$.

The degree of a vertex i in a hypergraph H is the number of edges containing i, denoted by $d_i(H)$. For $e\in E(H)$, let $d_e=\sum _{u\in e}d_u(H)$. We denote by $\Omega ^w(H)$ the weighted intersection graph [1] of H, which is obtained from $\Omega (H)$ by assigning the weight $|e_1\cap e_2|$ to each edge $\{e_1,e_2\}$ in $\Omega (H)$ ($\{e_1,e_2\}\subseteq E(H),|e_1\cap e_2|>0$).

Theorem 4.4

Let H be a connected hypergraph. Then,

$$\begin{aligned} t(\Omega ^w(H),w)=\frac{\prod _{e\in E(H)}d_e}{\prod _{u\in V(H)}d_u^2(H)}\sum _{T\in {\mathbb {T}}(H_{(2)})}\prod _{\{u,v\}\in E(T)}\left( \sum _{\{u,v\}\subseteq e\in E(H)}\frac{d_u(H)d_v(H)}{d_e}\right) . \end{aligned}$$

Proof

The expression of $t(\Omega ^w(H),w)$ is obtained when $w_e=1$ for each $e\in E(H)$ in Theorem 4.3. $\square$

For a linear hypergraph H, if $\{u,v\}\in E(H_{(2)})$, then there is a unique edge $e(u,v)\in E(H)$ containing u and v. So we have the following consequence from Theorem 4.3.

Theorem 4.5

Let H be a connected linear hypergraph, and the weights of $\Omega (H)$ are induced by indeterminates $\{w_e\}_{e\in E(H)}$. Then,

$$\begin{aligned} t(\Omega (H),w)=\frac{\prod _{e\in E(H)}(w_e\sum _{u\in e}d_u)}{\prod _{u\in V(H)}d_u^2}\sum _{T\in {\mathbb {T}}(H_{(2)})}\prod _{\{u,v\}\in E(T)}\frac{d_ud_vw_{e(u,v)}}{\sum _{i\in e(u,v)}d_i}, \end{aligned}$$

where $d_u=\sum _{u\in e\in E(H)}w_e$ and $e(u,v)\in E(H)$ is the unique edge containing u and v.

The following formula is obtained when $w_e=1$ for each $e\in E(H)$ in Theorem 4.5.

Corollary 4.6

Let H be a connected linear hypergraph. Then,

$$\begin{aligned} |{\mathbb {T}}(\Omega (H))|=\frac{\prod _{e\in E(H)}d_e}{\prod _{u\in V(H)}d_u^2(H)}\sum _{T\in {\mathbb {T}}(H_{(2)})}\prod _{\{u,v\}\in E(T)}\frac{d_u(H)d_v(H)}{d_{e(u,v)}}, \end{aligned}$$

where $e(u,v)\in E(H)$ is the unique edge containing u and v.

5 Spanning trees and clique partitions of graphs

For a clique partition $\varepsilon =\{Q_1,\ldots ,Q_r\}$ of graph G, let $S_u=\{Q_i:u\in Q_i\}$ denote the set of cliques containing the vertex u. Let $\Omega (\varepsilon )$ denote the clique graph with vertex set $\varepsilon =\{Q_1,\ldots ,Q_r\}$ and edge set $\{\{Q_i,Q_j\}:Q_i\cap Q_j\ne \emptyset \}$.

We first give the following clique partition formula of t(G, w) for a weighted graph G induced by its vertex weights.

Theorem 5.1

Let G be a connected weighted graph induced by indeterminates $\{w_i\}_{i\in V(G)}$. For a clique partition $\varepsilon =\{Q_1,\ldots ,Q_r\}$ of G, we have

$$\begin{aligned} t(G,w)=\frac{\prod _{u\in V(G)}(w_u\sum _{Q_i\in S_u}d_{Q_i})}{\prod _{i=1}^rd_{Q_i}^2}\sum _{T\in {\mathbb {T}}(\Omega (\varepsilon ))}\prod _{\{Q_i,Q_j\}\in E(T)}\frac{d_{Q_i}d_{Q_j}w_{\kappa (Q_i,Q_j)}}{\sum _{Q_u\in S_{\kappa (Q_i,Q_j)}}d_{Q_u}}, \end{aligned}$$

where $d_{Q_i}=\sum _{u\in Q_i}w_u$ and $\kappa (Q_i,Q_j)\in Q_i\cap Q_j$ is the unique common vertex of $Q_i$ and $Q_j$.

Proof

Let $H_\varepsilon$ be the linear hypergraph with vertex set $\varepsilon =\{Q_1,\ldots ,Q_r\}$ and edge set $\{S_u:u\in V(G)\}$. From Observation 2.1, we have $G=\Omega (H_\varepsilon )$. If each edge $\{S_u,S_v\}$ in $\Omega (H_\varepsilon )$ is weighted by $w_uw_v$, then $t(G,w)=t(\Omega (H_\varepsilon ),w)$. We can obtain the expression of t(G, w) from Theorem 4.5. $\square$

We can obtain the following clique partition formula for the number of spanning trees of a graph from the above theorem.

Theorem 5.2

Let $\varepsilon =\{Q_1,\ldots ,Q_r\}$ be a clique partition of a connected graph G. Then,

$$\begin{aligned} |{\mathbb {T}}(G)|=\frac{\prod _{u\in V(G)}f_u}{\prod _{i=1}^r|Q_i|^2}\sum _{T\in {\mathbb {T}}(\Omega (\varepsilon ))}\prod _{\{Q_i,Q_j\}\in E(T)}\frac{|Q_i||Q_j|}{f_{\kappa (Q_i,Q_j)}}, \end{aligned}$$

where $f_u=\sum _{Q_i\in S_u}|Q_i|=d_u(G)+|S_u|$, $\kappa (Q_i,Q_j)\in Q_i\cap Q_j$ is the unique common vertex of $Q_i$ and $Q_j$.

Proof

In Theorem 5.1, if $w_u=1$ for each $u\in V(G)$, then $d_{Q_i}=|Q_i|$ and $\sum _{Q_i\in S_u}|Q_i|=d_u(G)+|S_u|$. We can obtain the expression of $|{\mathbb {T}}(G)|$ from Theorem 5.1. $\square$

The following is an example for the clique partition formula in Theorem 5.2.

Example 5.3

Let G be the graph on $m+n$ vertices obtained by connecting p disjoin edges between two complete graphs $K_m$ and $K_n$. Then,

$$\begin{aligned} |{\mathbb {T}}(G)|=m^{m-p-1}n^{n-p-1}(mn+m+n)^{p-1}p. \end{aligned}$$

Proof

Clearly, G has a clique partition $\varepsilon =\{C_1,C_2,Q_1,\ldots ,Q_p\}$, where $|C_1|=m,|C_2|=n$, $Q_1,\ldots ,Q_p$ correspond to p disjoin edges between two cliques $C_1$ and $C_2$. By Theorem 5.2, we have

$$\begin{aligned} |{\mathbb {T}}(G)|=\frac{m^{m-p}n^{n-p}(m+2)^p(n+2)^p}{m^2n^24^p}t(\Omega (\varepsilon ),w), \end{aligned}$$

(5.1)

where the clique graph $\Omega (\varepsilon )$ is a complete bipartite graph with bipartition $\{C_1,C_2\}\cup \{Q_1,\ldots ,Q_p\}$, and the weights of edges $\{C_1,Q_t\}$ and $\{C_2,Q_t\}$ in $\Omega (\varepsilon )$ are $w_{C_1Q_t}=\frac{2m}{m+2}$, $w_{C_2Q_t}=\frac{2n}{n+2}$ ($t=1,\ldots ,p$). The weighted degree of $Q_t$ in $\Omega (\varepsilon )$ is $\frac{2m}{m+2}+\frac{2n}{n+2}=\frac{4(mn+m+n)}{(m+2)(n+2)}$. By Theorem 3.4, we have

$$\begin{aligned} t(\Omega (\varepsilon ),w)=\frac{4^p(mn+m+n)^p}{(m+2)^p(n+2)^p}\frac{w_{C_1Q_t}w_{C_2Q_t}p}{w_{C_1Q_t}+w_{C_2Q_t}}=\frac{4^p(mn+m+n)^{p-1}mnp}{(m+2)^p(n+2)^p}. \end{aligned}$$

By Eq. (5.1), we get $|{\mathbb {T}}(G)|=m^{m-p-1}n^{n-p-1}(mn+m+n)^{p-1}p$. $\square$

For a clique partition $\varepsilon =\{Q_1,\ldots ,Q_r\}$ of G, let $I(Q_i)=|\{u\in Q_i:|S_u|>1\}|$. We can express the number of spanning trees of G via the subgraph induced by vertex set $\{u\in V(G):|S_u|>1\}$ as follows:

Theorem 5.4

Let $\varepsilon =\{Q_1,\ldots ,Q_r\}$ ($r>1$) be a clique partition of a connected graph G. Then,

$$\begin{aligned} |{\mathbb {T}}(G)|=\prod _{|S_u|=1}(d_u(G)+1)\prod _{i=1}^r\frac{I(Q_i)}{|Q_i|}\sum _{T\in {\mathbb {T}}({\widetilde{G}})}\prod _{e\in E(T)}\frac{|Q_e|}{I(Q_e)}, \end{aligned}$$

where ${\widetilde{G}}$ is the subgraph of G induced by $\{u\in V(G):|S_u|>1\}$ and $Q_e$ is the unique clique in $\varepsilon$ containing e.

Proof

Let $P_i=\{u:u\in Q_i,|S_u|>1\}$, and let H be the linear hypergraph with vertex set $V(H)=\{u\in V(G):|S_u|>1\}$ and edge set $E(H)=\{P_1,\ldots ,P_r\}$. Then, the clique graph $\Omega (\varepsilon )=\Omega (H)$ is the intersection graph of H, and the 2-section graph $H_{(2)}$ is the subgraph of G induced by V(H). For $u\in V(H)$ and $P_i\ni u$, we assign weight $|Q_i|$ to the edge $\{u,P_i\}$ in the incidence graph $I_H$. By Theorem 4.2, we have

$$\begin{aligned} t(I_H,w)= & {} \prod _{u\in V(H)}f_u\sum _{T\in {\mathbb {T}}(\Omega (\varepsilon ))}\prod _{\{Q_i,Q_j\}\in E(T)}\frac{|Q_i||Q_j|}{f_{\kappa (Q_i,Q_j)}}\\= & {} \prod _{i=1}^rI(Q_i)|Q_i|\sum _{T\in {\mathbb {T}}(H_{(2)})}\prod _{e\in E(T)}\frac{|Q_e|^2}{I(Q_e)|Q_e|}, \end{aligned}$$

where $f_u=\sum _{Q_i\in S_u}|Q_i|=d_u(G)+|S_u|$, $\kappa (Q_i,Q_j)\in Q_i\cap Q_j$ is the unique common vertex of $Q_i$ and $Q_j$. By Theorem 5.2, we have

$$\begin{aligned} |{\mathbb {T}}(G)|= & {} \frac{\prod _{u\in V(G)}f_u}{\prod _{i=1}^r|Q_i|^2}\sum _{T\in {\mathbb {T}}(\Omega (\varepsilon ))}\prod _{\{Q_i,Q_j\}\in E(T)}\frac{|Q_i||Q_j|}{f_{\kappa (Q_i,Q_j)}}\\= & {} \frac{\prod _{|S_u|=1}(d_u(G)+1)}{\prod _{i=1}^r|Q_i|^2}t(I_H,w)\\= & {} \prod _{|S_u|=1}(d_u(G)+1)\prod _{i=1}^r\frac{I(Q_i)}{|Q_i|}\sum _{T\in {\mathbb {T}}(H_{(2)})}\prod _{e\in E(T)}\frac{|Q_e|}{I(Q_e)}. \end{aligned}$$

$\square$

Theorem 5.4 yields the following formula for the number of spanning trees in an edge-clique extension of a graph.

Corollary 5.5

Let G be a connected graph with n vertices and m edges, and let ${\widetilde{G}}$ be the graph obtained from G by replacing each $e\in E(G)$ by a clique $Q_e$. Then,

$$\begin{aligned} |{\mathbb {T}}({\widetilde{G}})|=2^{m-n+1}\prod _{e\in E(G)}|Q_e|^{|Q_e|-3}\sum _{T\in {\mathbb {T}}(G)}\prod _{e\in E(T)}|Q_e|. \end{aligned}$$

Proof

The formula holds when $m=1$. So we assume that $m>1$. Note that $\{Q_e\}_{e\in E(G)}$ is a clique partition of ${\widetilde{G}}$ and $\{u\in V({\widetilde{G}}):|S_u|>1\}=\{u\in V(G):d_u(G)>1\}$. Let $G_0$ be the induced subgraph of G obtained by deleting all pendant vertices of G. Then, each spanning tree in $G_0$ has $n-|P(G)|-1$ edges, where P(G) is the set of pendant edges of G. By Theorem 5.4, we have

$$\begin{aligned} |{\mathbb {T}}({\widetilde{G}})|= & {} \frac{2^{m-|P(G)|}\prod _{e\in E(G)}|Q_e|^{|Q_e|-2}\prod _{e\in P(G)}|Q_e|}{\prod _{e\in E(G)}|Q_e|}\sum _{T\in {\mathbb {T}}(G_0)}\prod _{e\in E(T)}\frac{|Q_e|}{2}\\= & {} 2^{m-n+1}\prod _{e\in E(G)}|Q_e|^{|Q_e|-3}\sum _{T\in {\mathbb {T}}(G)}\prod _{e\in E(T)}|Q_e|. \end{aligned}$$

$\square$

The following formula can be derived from Corollary 5.5.

Corollary 5.6

Let ${\widetilde{G}}$ be the graph obtained from a connected graph G by replacing an edge $e\in E(G)$ by $K_s$. Then,

$$\begin{aligned} |{\mathbb {T}}({\widetilde{G}})|=s^{s-2}|{\mathbb {T}}(G)|-s^{s-3}(s-2)|{\mathbb {T}}(G-e)|. \end{aligned}$$

Proof

Let $n=|V(G)|,m=|E(G)|$. By Corollary 5.5, we have

$$\begin{aligned} |{\mathbb {T}}({\widetilde{G}})|= & {} 2^{m-n+1}2^{-(m-1)}s^{s-3}(2^{n-1}|{\mathbb {T}}(G-e)|+2^{n-2}s|{\mathbb {T}}_e(G)|)\\= & {} s^{s-3}(2|{\mathbb {T}}(G-e)|+s|{\mathbb {T}}_e(G)|), \end{aligned}$$

where ${\mathbb {T}}_e(G)\subseteq {\mathbb {T}}(G)$ is the set of spanning trees containing e. Since $|{\mathbb {T}}_e(G)|=|{\mathbb {T}}(G)|-|{\mathbb {T}}(G-e)|$, we get

$$\begin{aligned} |{\mathbb {T}}({\widetilde{G}})|=s^{s-2}|{\mathbb {T}}(G)|-s^{s-3}(s-2)|{\mathbb {T}}(G-e)|. \end{aligned}$$

$\square$

Given a sequence $\{G_n\}_{n\ge 1}$ of graphs, the limit $\lim _{|V(G_n)|\rightarrow \infty }\frac{\log |{\mathbb {T}}(G_n)|}{|V(G_n)|}$ when it exists is called the asymptotic growth constant [25] of the spanning trees of $\{G_n\}_{n\ge 1}$. In the following example, we use Corollary 5.6 to obtain the number and asymptotic growth constant of the spanning trees of Fan graphs.

Example 5.7

The Fan graph $F_n=K_1\vee P_n$ is the join of an isolated vertex $K_1$ and a path $P_n$ with n vertices. Since $F_n$ can be obtained from $F_{n-1}$ by replacing an edge of $F_{n-1}$ by $K_3$, by Corollary 5.6, we have

$$\begin{aligned} |{\mathbb {T}}(F_n)|=3|{\mathbb {T}}(F_{n-1})|-|{\mathbb {T}}(F_{n-2})|. \end{aligned}$$

Solving this recurrence relation, we get

$$\begin{aligned} |{\mathbb {T}}(F_n)|=5^{-\frac{1}{2}}\left[ \left( \frac{3+\sqrt{5}}{2}\right) ^n-\left( \frac{3-\sqrt{5}}{2}\right) ^n\right] . \end{aligned}$$

The asymptotic growth constant of the spanning trees of $\{F_n\}_{n\ge 1}$ is

$$\begin{aligned} \lim _{n\rightarrow \infty }\frac{\log |{\mathbb {T}}(F_n)|}{n+1}=\log \frac{3+\sqrt{5}}{2}. \end{aligned}$$

6 Applications

In this section, as applications of our work, we derive formulas for the enumeration of spanning trees in bipartite graphs, line graphs, generalized line graphs, middle graphs, total graphs and generalized join graphs.

6.1 Bipartite graphs

We can get the following formula for the number of spanning trees in a bipartite graph from Theorem 3.4.

Theorem 6.1

Let G be a connected bipartite graph with a bipartition $V(G)=V_1\cup V_2$. Then,

$$\begin{aligned} |{\mathbb {T}}(G)|= & {} \prod _{i\in V_1}d_i(G)\sum _{T\in {\mathbb {T}}(G(V_2))}\prod _{\{u,v\}\in E(T)}\left( \sum _{i\in N_G(u)\cap N_G(v)}\frac{1}{d_i(G)}\right) \\= & {} \prod _{i\in V_2}d_i(G)\sum _{T\in {\mathbb {T}}(G(V_1))}\prod _{\{u,v\}\in E(T)}\left( \sum _{i\in N_G(u)\cap N_G(v)}\frac{1}{d_i(G)}\right) , \end{aligned}$$

where $G(V_k)$ has edge set

$$\begin{aligned} \{\{u,v\}:u\ne v,u,v\in V_k,N_G(u)\cap N_G(v)\ne \emptyset \}~(k=1,2). \end{aligned}$$

The following expression for enumerating spanning trees in an incidence graph is obtained when $w_{ue}=1$ in Theorem 4.2.

Theorem 6.2

Let H be a connected hypergraph. Then,

$$\begin{aligned} |{\mathbb {T}}(I_H)|=\prod _{e\in E(H)}|e|\sum _{T\in {\mathbb {T}}(H_{(2)})}\prod _{\{u,v\}\in E(T)}\left( \sum _{\{u,v\}\subseteq e\in E(H)}|e|^{-1}\right) . \end{aligned}$$

A hypergraph H is called k-uniform if $|e|=k$ for each $e\in E(H)$. A 2-$(v,k,\lambda )$ design can be regarded as a k-uniform regular hypergraph H of degree $r=\frac{\lambda (v-1)}{k-1}$ on v vertices, and $|\{e\in E(H): x,y\in e\}|=\lambda$ for any pair of distinct $x,y\in V(H)$ (see [4]).

Example 6.3

Let H be a 2-$(v,k,\lambda )$ design. By Theorem 6.2, we have

$$\begin{aligned} |{\mathbb {T}}(I_H)|=k^{b-v+1}\lambda ^{v-1}v^{v-2}, \end{aligned}$$

where $b=\frac{\lambda v(v-1)}{k(k-1)}$.

The following formula is obtained from Theorem 6.2.

Corollary 6.4

Let H be a k-uniform linear hypergraph with n vertices and m edges. Then,

$$\begin{aligned} |{\mathbb {T}}(I_H)|=k^{m-n+1}|{\mathbb {T}}(H_{(2)})|. \end{aligned}$$

The subdivision graph S(G) of a graph G is obtained from G by substituting each edge of G with a path of length 2. Note that S(G) can be regarded as the incidence graph of G. So the following formula follows from Corollary 6.4.

Corollary 6.5

[23] Let G be a graph with n vertices and m edges. Then

$$\begin{aligned} |{\mathbb {T}}(S(G))|=2^{m-n+1}|{\mathbb {T}}(G)|. \end{aligned}$$

6.2 Line graphs

The line graph ${\mathcal {L}}(G)$ of G has vertex set $V({\mathcal {L}}(G))=E(G)$, and two vertices in ${\mathcal {L}}(G)$ are adjacent if and only if their corresponding edges have common vertex in G.

A classical theorem of graph spectra tells us the relation between the number of spanning trees of a regular graph G and its line graph ${\mathcal {L}}(G)$ as follows:

Theorem 6.6

[3] Let G be a d-regular graph with n vertices and m edges. Then,

$$\begin{aligned} |{\mathbb {T}}({\mathcal {L}}(G))|=2^{m-n+1}d^{m-n-1}|{\mathbb {T}}(G)|. \end{aligned}$$

A bipartite graph G with bipartition $V(G)=V_1\cup V_2$ is called $(q_1+1,q_2+1)$-semiregular if $d_u(G)=q_i+1$ for $u\in V_i$ ($i=1,2$).

Theorem 6.7

[28] Let G be a connected $(q_1+1,q_2+1)$-semiregular graph with bipartition $V(G)=V_1\cup V_2$ ($|V_1|\le |V_2|$). Then,

$$\begin{aligned} |{\mathbb {T}}({\mathcal {L}}(G))|=\frac{|V_1|q_1-|V_2|}{|V_1|(q_1+1)}\frac{(q_1+q_2+2)^{|E(G)|-|V(G)|+1}}{q_1q_2-1}\left( \frac{q_1+1}{q_2+1}\right) ^{|V_2|-|V_1|}|{\mathbb {T}}(G)|. \end{aligned}$$

When G is regular, Zhang et al. [33] gave the following expression for the line graph of the subdivision graph S(G) as follows.

Theorem 6.8

[33] Let G be a d-regular graph with n vertices and m edges. Then,

$$\begin{aligned} |{\mathbb {T}}({\mathcal {L}}(S(G)))|=d^{m-n-1}(d+2)^{m-n+1}|{\mathbb {T}}(G)|. \end{aligned}$$

In 2013, Yan [31] gave the formula of the number of spanning trees of a class of irregular line graphs as follows:

Theorem 6.9

[31] Let G be a connected graph with $n+s$ vertices and $m+s$ edges in which n vertices have degree k and s vertices have degree 1. Then,

$$\begin{aligned} |{\mathbb {T}}({\mathcal {L}}(G))|=2^{m-n+1}k^{m+s-n-1}|{\mathbb {T}}(G)|. \end{aligned}$$

In 2017, Dong and Yan [14] gave the formula of the number of spanning trees of general line graphs as follows:

Theorem 6.10

[14] Let G be a connected graph. Then,

$$\begin{aligned} |{\mathbb {T}}({\mathcal {L}}(G))|=\prod _{i\in V(G)}d_i(G)^{d_i(G)-2}\sum _{T\in {\mathbb {T}}(G)}\prod _{\{u,v\}\in E(G)\backslash E(T)}\frac{d_u(G)+d_v(G)}{d_u(G)d_v(G)}. \end{aligned}$$

In 2018, Gong and Jin [20] gave a simple formula equivalent to Theorem 6.10 as follows:

Theorem 6.11

[20] Let G be a connected graph. Then,

$$\begin{aligned} |{\mathbb {T}}({\mathcal {L}}(G))|=\frac{\prod _{\{u,v\}\in E(G)}(d_u(G)+d_v(G))}{\prod _{i\in V(G)}d_i(G)^2}\sum _{T\in {\mathbb {T}}(G)}\prod _{\{u,v\}\in E(T)}\frac{d_u(G)d_v(G)}{d_u(G)+d_v(G)}. \end{aligned}$$

We extend the above several formulas as follows, which is a special case of Theorem 4.5.

Theorem 6.12

Let $\{w_e\}_{e\in E(G)}$ be indeterminates on the edge set of a connected graph G, and the weights of ${\mathcal {L}}(G)$ are induced by $\{w_e\}_{e\in E(G)}$. Then,

$$\begin{aligned} t({\mathcal {L}}(G),w)=\frac{\prod _{\{u,v\}\in E(G)}w_{uv}(d_u(G)+d_v(G))}{\prod _{i\in V(G)}d_i(G)^2}\sum _{T\in {\mathbb {T}}(G)}\prod _{\{u,v\}\in E(T)}\frac{w_{uv}d_u(G)d_v(G)}{d_u(G)+d_v(G)}, \end{aligned}$$

where $d_i(G)=\sum _{j\in V(G)}w_{ij}(G)$.

Proof

Note that ${\mathcal {L}}(G)$ is the intersection graph of G. We can obtain the expression of $t({\mathcal {L}}(G),w)$ from Theorem 4.5. $\square$

Remark 6.13

For a vertex u of graph G, all edges incident to u form a clique in ${\mathcal {L}}(G)$, and all such cliques form a natural clique partition of ${\mathcal {L}}(G)$. By considering this natural clique partition, we can also get Theorem 6.12 from Theorem 5.1.

6.3 Middle graphs

The middle graph [32] M(G) is obtained from G by inserting a new vertex into each edge of G, then joining with edges those pairs of new vertices on adjacent edges of G. Then M(G) has vertex set $V(G)\cup E(G)$ and edge set $E({\mathcal {L}}(G))\cup E(S(G))$, where S(G) is the subdivision graph of G.

Sato [29] gave the following relation between the number of spanning trees of a semiregular graph and its middle graph.

Theorem 6.14

[29] Let G be a connected $(q_1+1,q_2+1)$-semiregular graph with bipartition $V(G)=V_1\cup V_2$. Then

$$\begin{aligned} |{\mathbb {T}}(M(G))|=(q_1+2)^{|V_2|-1}(q_2+2)^{|V_1|-1}(q_1+q_2+4)^{|E(G)|-|V(G)|+1}|{\mathbb {T}}(G)|. \end{aligned}$$

Huang and Li [23] obtained the relation between the number of spanning trees of a regular graph and its middle graph as follows.

Theorem 6.15

[23] Let G be a d-regular graph with n vertices and m edges. Then,

$$\begin{aligned} |{\mathbb {T}}(M(G))|=2^{m-n+1}(d+1)^{m-1}|{\mathbb {T}}(G)|. \end{aligned}$$

In 2017, Yan [32] gave the formula of the number of spanning trees of general middle graphs as follows:

Theorem 6.16

[32] Let G be a connected graph. Then

$$\begin{aligned} |{\mathbb {T}}(M(G))|=\frac{\prod _{\{u,v\}\in E(G)}(f_u+f_v)}{\prod _{i\in V(G)}f_i}\sum _{T\in {\mathbb {T}}(G)}\prod _{\{u,v\}\in E(T)}\frac{f_uf_v}{f_u+f_v}, \end{aligned}$$

where $f_u=d_u(G)+1$.

We extend the above formulas as follows, which is a special case of Theorem 4.5.

Theorem 6.17

Let $\{w_u\}_{u\in V(G)}$ and $\{w_e\}_{e\in E(G)}$ be indeterminates on the vertex set and edge set of a connected graph G, respectively. The weights of M(G) are induced by $\{w_u\}_{u\in V(G)}$ and $\{w_e\}_{e\in E(G)}$. Then,

$$\begin{aligned} t(M(G),w)=\frac{\prod _{u\in V(G)}w_u\prod _{\{u,v\}\in E(G)}w_{uv}(f_u+f_v)}{\prod _{i\in V(G)}f_i}\sum _{T\in {\mathbb {T}}(G)}\prod _{\{u,v\}\in E(T)}\frac{w_{uv}f_uf_v}{f_u+f_v}, \end{aligned}$$

where $f_i=w_i+\sum _{j\in V(G)}w_{ij}(G)$.

Proof

Let H be the linear hypergraph with vertex set $V(H)=V(G)$ and edge set $E(H)=E(G)\cup \{\{u\}:u\in V(G)\}$. Note that M(G) is the intersection graph of H. We can obtain the expression of t(M(G), w) from Theorem 4.5. $\square$

Remark 6.18

For a vertex u of graph G, u and all edges incident to u form a clique in M(G), and all such cliques form a natural clique partition of M(G). By considering this natural clique partition, we can also get Theorem 6.17 from Theorem 5.1.

6.4 Total graphs

The total graph ${\mathcal {T}}(G)$ of G has vertex set $V({\mathcal {T}}(G))=V(G)\cup E(G)$, and two vertices in ${\mathcal {T}}(G)$ are adjacent if and only if their corresponding elements are either adjacent or incident in G.

The research on spanning trees in line graphs and middle graphs leads us to the study of total graphs naturally. We give the formula for the number of spanning trees in a total graph as follows:

Theorem 6.19

Let G be a graph with vertex set $\{1,\ldots ,n\}$. For any $p,q\in \{1,\ldots ,n\}$, we have

$$\begin{aligned} |{\mathbb {T}}({\mathcal {T}}(G))|=\frac{(-1)^{p+q}\det (F(p,q))}{\prod _{u\in V(G)}(d_u(G)+1)}\prod _{\{u,v\}\in E(G)}(d_u(G)+d_v(G)+2), \end{aligned}$$

where $F=L_{{\widetilde{G}}}(D_G+I)^{-1}L_G+L_G+L_{{\widetilde{G}}}$, ${\widetilde{G}}$ is the weighted graph obtained from G by assigning weight $w_{uv}({\widetilde{G}})=\frac{(d_u(G)+1)(d_v(G)+1)}{d_u(G)+d_v(G)+2}$ to each $\{u,v\}\in E(G)$.

Proof

For $u\in V(G)$, let $Q_u=\{u\}\cup \{e:u\in e\in E(G)\}$. Then, $\{Q_u\}_{u\in V(G)}$ are edge disjoint cliques in ${\mathcal {T}}(G)$. For all $Q_u$ in ${\mathcal {T}}(G)$, we implement the local transformation described in Corollary 3.6 successively (take $U=Q_u$ in Corollary 3.6). Then, we obtain a weighted graph H satisfying

$$\begin{aligned} t(H,w)=|{\mathbb {T}}({\mathcal {T}}(G))|\prod _{u\in V(G)}|Q_u|^2=|{\mathbb {T}}({\mathcal {T}}(G))|\prod _{u\in V(G)}(d_u(G)+1)^2, \end{aligned}$$

(6.1)

and the Laplacian matrix of H is

$$\begin{aligned} L_H=\begin{pmatrix}C&{}0&{}-B^\top \\ 0&{}L_G+D_G+I&{}-(D_G+I)\\ -B&{}-(D_G+I)&{}(D_G+I)^2\end{pmatrix}, \end{aligned}$$

where C is a diagonal matrix of order |E(G)| with diagonal entries $C_{ee}=d_u(G)+d_v(G)+2$ ($e=\{u,v\}\in E(G)$), B is a $n\times |E(G)|$ matrix with entries $(B)_{ie}=d_i(G)+1$ if the vertex i is incident to the edge e, and $(B)_{ie}=0$ otherwise.

The Schur complement of C in $L_H$ is

$$\begin{aligned} S= & {} \begin{pmatrix}L_G+D_G+I&{}-(D_G+I)\\ -(D_G+I)&{}(D_G+I)^2\end{pmatrix}-\begin{pmatrix}0\\ -B\end{pmatrix}C^{-1}\begin{pmatrix}0&-B^\top \end{pmatrix}\\= & {} \begin{pmatrix}L_G+D_G+I&{}-(D_G+I)\\ -(D_G+I)&{}L_{{\widetilde{G}}}+D_G+I\end{pmatrix}, \end{aligned}$$

where ${\widetilde{G}}$ is the weighted graph obtained from G by assigning weight $w_{uv}({\widetilde{G}})=\frac{(d_u(G)+1)(d_v(G)+1)}{d_u(G)+d_v(G)+2}$ to each $\{u,v\}\in E(G)$. Let G(S) be the Schur complement weighted graph with Laplacian matrix S. By Proposition 3.1, we have

$$\begin{aligned} t(H,w)=\det (C)t(G(S),w)=t(G(S),w)\prod _{\{u,v\}\in E(G)}(d_u(G)+d_v(G)+2).\nonumber \\ \end{aligned}$$

(6.2)

For any $p\in V({\widetilde{G}}),q\in V(G)$, by Lemma 2.4, we have

$$\begin{aligned} t(G(S),w)=(-1)^{n+p+q}\det (S(n+p,q)). \end{aligned}$$

Let $S_0=\begin{pmatrix}-(D_G+I)&{}L_G+D_G+I\\ L_{{\widetilde{G}}}+D_G+I&{}-(D_G+I)\end{pmatrix}$, then we have

$$\begin{aligned} \det (S(n+p,q))=(-1)^{n(n-1)}\det (S_0(n+p,n+q)) \end{aligned}$$

and

$$\begin{aligned} t(G(S),w)=(-1)^{n+p+q}\det (S_0(n+p,n+q)). \end{aligned}$$

(6.3)

The Schur complement of $-(D_G+I)$ in $S_0$ is

$$\begin{aligned} F= & {} -(D_G+I)+(L_{{\widetilde{G}}}+D_G+I)(D_G+I)^{-1}(L_G+D_G+I)\\= & {} L_{{\widetilde{G}}}(D_G+I)^{-1}L_G+L_G+L_{{\widetilde{G}}}. \end{aligned}$$

By Lemma 2.6, we have

$$\begin{aligned} \det (S_0(n+p,n+q))= & {} \det (-(D_G+I))\det (F(p,q))\\= & {} (-1)^n\det (F(p,q))\prod _{u\in V(G)}(d_u(G)+1). \end{aligned}$$

By Eq. (6.3), we have

$$\begin{aligned} t(G(S),w)=(-1)^{p+q}\det (F(p,q))\prod _{u\in V(G)}(d_u(G)+1). \end{aligned}$$

(6.4)

By Eqs. (6.1), (6.2) and (6.4), we have

$$\begin{aligned} |{\mathbb {T}}({\mathcal {T}}(G))|= & {} \left( \prod _{u\in V(G)}(d_u(G)+1)^{-2}\right) t(H,w)\\= & {} \frac{(-1)^{p+q}\det (F(p,q))}{\prod _{u\in V(G)}(d_u(G)+1)}\prod _{\{u,v\}\in E(G)}(d_u(G)+d_v(G)+2). \end{aligned}$$

$\square$

When G is regular, $|{\mathbb {T}}({\mathcal {T}}(G))|$ can be obtained from $|{\mathbb {T}}(G)|$ and Laplacian eigenvalues of G.

Corollary 6.20

Let G be a d-regular connected graph with n vertices and m edges. Then,

$$\begin{aligned} |{\mathbb {T}}({\mathcal {T}}(G))|=2^{m-n+1}(d+1)^{m-n}\left( \prod _{i=1}^{n-1}(\mu _i(G)+d+3)\right) |{\mathbb {T}}(G)|. \end{aligned}$$

Proof

Since G is d-regular, the matrices $L_{{\widetilde{G}}}$ and F in Theorem 6.19 are

$$\begin{aligned} L_{{\widetilde{G}}}=\frac{d+1}{2}L_G,~F=(d+1)^{-1}L_{{\widetilde{G}}}L_G+L_G+L_{{\widetilde{G}}}=\frac{1}{2}L_G^2+\frac{d+3}{2}L_G. \end{aligned}$$

Let $\mu _1=\mu _1(G)\ge \cdots \ge \mu _{n-1}=\mu _{n-1}(G)>0$ be all nonzero eigenvalues of $L_G$, then $\frac{1}{2}\mu _i^2+\frac{d+3}{2}\mu _i$ ($i=1,\ldots ,n-1$) are all nonzero eigenvalues of F. Theorem 6.19 implies that $\det (F(p,p))$ is independent of the choice of p. So $\prod _{i=1}^{n-1}\left( \frac{1}{2}\mu _i^2+\frac{d+3}{2}\mu _i\right) =\sum _{p=1}^n\det (F(p,p))=n\det (F(p,p))$. By Lemma 2.4, we have

$$\begin{aligned} \det (F(p,p))=\frac{1}{n}\prod _{i=1}^{n-1}\left( \frac{1}{2}\mu _i^2+\frac{d+3}{2}\mu _i\right) =2^{-(n-1)}\left( \prod _{i=1}^{n-1}(\mu _i+d+3)\right) |{\mathbb {T}}(G)|. \end{aligned}$$

By Theorem 6.19, we have

$$\begin{aligned} |{\mathbb {T}}({\mathcal {T}}(G))|= & {} \frac{\det (F(p,p))}{(d+1)^n}(2(d+1))^m\\= & {} 2^{m-n+1}(d+1)^{m-n}\left( \prod _{i=1}^{n-1}(\mu _i+d+3)\right) |{\mathbb {T}}(G)|. \end{aligned}$$

$\square$

Example 6.21

Let $K_{1,n}$ be the star with n edges. Then,

$$\begin{aligned} |{\mathbb {T}}({\mathcal {T}}(K_{1,n}))|=3(2n+3)^{n-1}. \end{aligned}$$

Proof

The Laplacian matrix of $G=K_{1,n}$ is $L_G=\begin{pmatrix}I&{}-\text{ j}_n\\ -\text{ j}_n^\top &{}n\end{pmatrix}$, where $\text{ j}_n$ denotes an all-ones vector of dimension n. The weighted graph ${\widetilde{G}}$ defined in Theorem 6.19 has Laplacian matrix $L_{{\widetilde{G}}}=\begin{pmatrix}\frac{2(n+1)}{n+3}I&{}-\frac{2(n+1)}{n+3}\text{ j}_n\\ -\frac{2(n+1)}{n+3}\text{ j}_n^\top &{}\frac{2n(n+1)}{n+3}\end{pmatrix}$. By computation, the matrix F in Theorem 6.19 is

$$\begin{aligned} F=L_{{\widetilde{G}}}\begin{pmatrix}2^{-1}I&{}0\\ 0&{}(n+1)^{-1}\end{pmatrix}L_G+L_G+L_{{\widetilde{G}}} =\begin{pmatrix}\frac{4n+6}{n+3}I+\frac{2}{n+3}J_n&{}-\frac{6(n+1)}{n+3}\text{ j}_n\\ -\frac{6(n+1)}{n+3}\text{ j}_n^\top &{}\frac{6n(n+1)}{n+3}\end{pmatrix}, \end{aligned}$$

where $J_n$ denotes an all-ones matrix of order n. By Theorem 6.19, we have

$$\begin{aligned} |{\mathbb {T}}({\mathcal {T}}(K_{1,n}))|= & {} \det \left( \frac{4n+6}{n+3}I+\frac{2}{n+3}J_n\right) 2^{-n}(n+1)^{-1}(n+3)^n\\= & {} \frac{6(n+1)}{n+3}\left( \frac{4n+6}{n+3}\right) ^{n-1}2^{-n}(n+1)^{-1}(n+3)^n=3(2n+3)^{n-1}. \end{aligned}$$

$\square$

6.5 Generalized join graphs

Let G be a graph with n vertices. The generalized join graph $G[H_1,\ldots ,H_n]$ is obtained from G by replacing each $u\in V(G)$ by a graph $H_u$, and for $x\in V(H_u)$ and $y\in V(H_v)$ ($u\ne v$), x and y are adjacent in $G[H_1,\ldots ,H_n]$ if and only if $\{u,v\}\in E(G)$. For example, if $G,\overline{H_1},\ldots ,\overline{H_n}$ are complete graphs, then $G[H_1,\ldots ,H_n]$ is a complete multipartite graph.

We give an expression of $|{\mathbb {T}}(G[H_1,\ldots ,H_n])|$ in terms of Laplacian eigenvalues of $H_1,\ldots ,H_n$ and spanning trees of G as follows:

Theorem 6.22

Let $G_0=G[H_1,\ldots ,H_n]$ be a generalized join graph, where $G,H_1,\ldots ,H_n$ are connected. Then,

$$\begin{aligned} |{\mathbb {T}}(G_0)|=\prod _{u\in V(G)}\frac{\prod _{i=1}^{m_u-1}\left( \mu _i(H_u)+\sum _{v\in N_G(u)}m_v\right) }{m_u}\sum _{T\in {\mathbb {T}}(G)}\prod _{\{u,v\}\in E(T)}m_um_v, \end{aligned}$$

where $m_u=|V(H_u)|$.

Proof

For $e=\{u,v\}\in E(G)$, let $Q_e=V(H_u)\cup V(H_v)$ and let $w_e=m_u+m_v$. For all vertex subset $Q_e$ in $G_0$, we implement the local transformation described in Corollary 3.6 successively (take $U=Q_e$ in Corollary 3.6). Then, we obtain a weighted graph H satisfying

$$\begin{aligned} t(H,w)=|{\mathbb {T}}(G_0)|\prod _{e\in E(G)}|Q_e|^2=|{\mathbb {T}}(G_0)|\prod _{e\in E(G)}w_e^2, \end{aligned}$$

(6.8)

and the Laplacian matrix of H is $L_H=\begin{pmatrix}C&{}-B^\top \\ -B&{}E\end{pmatrix}$, where C is a diagonal matrix of order |E(G)| with diagonal entries $C_{ee}=w_e^2$, $E=\text{ diag }(E_1,\ldots ,E_n)$ is a block diagonal matrix such that

$$\begin{aligned} E_i =L_{H_i}-d_i(G)(m_iI-J_{m_i})+\left( \sum _{e\ni i}w_e\right) I=L_{H_i}+\left( \sum _{v\in N_G(i)}m_v\right) I+d_i(G)J_{m_i}, \end{aligned}$$

B is a $(\sum _{i=1}^nm_i)\times |E(G)|$ matrix with entries $(B)_{ie}=w_e$ if $i\in V(H_u)$ and u is incident to e in G, and $(B)_{ie}=0$ otherwise.

By Lemma 2.5, we have

$$\begin{aligned} \det (E_u)=\sum _{e\ni u}w_e\prod _{i=1}^{m_u-1}\left( \mu _i(H_u)+\sum _{v\in N_G(u)}m_v\right) ,~\text{ j}_{m_u}^\top E_u^{-1}\text{ j}_{m_u}=\frac{m_u}{\sum _{e\ni i}w_e}. \end{aligned}$$

(6.9)

The Schur complement of E in $L_H$ is $S=C-B^\top E^{-1}B$. For any two edges e and f in G, by computation, we have

$$\begin{aligned} (B^\top E^{-1}B)_{ef}={\left\{ \begin{array}{ll}0\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad ~~&{}\text{ if }~e\cap f=\emptyset ,\\ w_ew_f\text{ j}_{m_k}^\top E_k^{-1}\text{ j}_{m_k}=\frac{m_kw_ew_f}{\sum _{e\ni k}w_e}\qquad \qquad &{}\text{ if }~e\cap f=\{k\}.\end{array}\right. } \end{aligned}$$

For $e\cap f=\{k\}$, we assign weight $\frac{m_kw_ew_f}{\sum _{e\ni k}w_e}$ to the edge $\{e,f\}$ in the line graph ${\mathcal {L}}(G)$. Then S is the Laplacian matrix of the weighted line graph ${\mathcal {L}}(G)$. By Proposition 3.1, we have

$$\begin{aligned} t(H,w)&=\det (E)t({\mathcal {L}}(G),w) \nonumber \\&=\prod _{u\in V(G)}\det (E_u)\sum _{T\in {\mathbb {T}}({\mathcal {L}}(G))}\prod _{\{e,f\}\in E(T)}\frac{m_{k(e,f)}w_ew_f}{\sum _{e\ni \kappa (e,f)}w_e}, \end{aligned}$$

(6.10)

where $\kappa (e,f)$ denotes the unique common vertex of e and f. Note that ${\mathcal {L}}(G)=\Omega (G)$ is the intersection graph of G. Take $w_{ue}=m_uw_e$ in Theorem 4.2, we get

$$\begin{aligned}&\prod _{u\in V(G)}\left( m_u\sum _{e\ni u}w_e\right) \sum _{T\in {\mathbb {T}}({\mathcal {L}}(G)}\prod _{\{e,f\}\in E(T)}\frac{m_{k(e,f)}w_ew_f}{\sum _{e\ni k(e,f)}w_e}\\&\quad =\prod _{e\in E(G)}w_e^2\sum _{T\in {\mathbb {T}}(G)}\prod _{\{u,v\}\in E(T)}m_um_v. \end{aligned}$$

(6.11)

The expression of $|{\mathbb {T}}(G_0)|$ follows from Eqs. (6.8)–(6.11). $\square$

If $H_u=H$ for each $u\in V(G)$, then $G[H_1,\ldots ,H_n]$ is the lexicographic product of G and H, denoted by G[H]. By Theorem 6.22, we get the following two known results (see Theorem 6.7 and Corollary 6.8 in [19]).

Corollary 6.23

[19] Let $G_0=G[H_1,\ldots ,H_n]$ be a generalized join graph, where $G,H_1,\ldots ,H_n$ are connected. If $|V(H_u)|=m$ for each $u\in V(G)$, then

$$\begin{aligned} |{\mathbb {T}}(G_0)|=m^{n-2}\left( \prod _{u\in V(G)}\prod _{i=1}^{m-1}\left( \mu _i(H_u)+md_u(G)\right) \right) |{\mathbb {T}}(G)|. \end{aligned}$$

Corollary 6.24

[19] Let G and H be connected graphs with n vertices and m vertices, respectively. Then,

$$\begin{aligned} |{\mathbb {T}}(G[H])|=m^{n-2}\left( \prod _{u\in V(G)}\prod _{i=1}^{m-1}\left( \mu _i(H)+md_u(G)\right) \right) |{\mathbb {T}}(G)|. \end{aligned}$$

If $G=K_2$, then $G[H_1,H_2]=H_1\vee H_2$ is the join of $H_1$ and $H_2$. Theorem 6.22 yields the following formula for the number of spanning trees in a join graph.

Corollary 6.25

Let $H_1$ and $H_2$ be graphs with $m_1$ and $m_2$ vertices, respectively. Then,

$$\begin{aligned} |{\mathbb {T}}(H_1\vee H_2)|=\prod _{i=1}^{m_1-1}\left( \mu _i(H_1)+m_2\right) \prod _{i=1}^{m_2-1}\left( \mu _i(H_2)+m_1\right) . \end{aligned}$$

Example 6.26

The generalized join graph $G_0=G[H_1,\ldots ,H_n]$ is called a clique extension [22] of G if $H_1=K_{m_1},\ldots ,H_n=K_{m_n}$ are complete graphs. The Laplacian eigenvalues of $H_i=K_{m_i}$ are

$$\begin{aligned} \mu _1(H_i)=\cdots =\mu _{m_i-1}(H_i)=m_i,~\mu _{m_i}(H_i)=0. \end{aligned}$$

By Theorem 6.22, we get

$$\begin{aligned} |{\mathbb {T}}(G_0)|=\prod _{u\in V(G)}\frac{\left( m_u+\sum _{v\in N_G(u)}m_v\right) ^{m_u-1}}{m_u}\sum _{T\in {\mathbb {T}}(G)}\prod _{\{u,v\}\in E(T)}m_um_v. \end{aligned}$$

If $m_1=\cdots =m_n=m$, then

$$\begin{aligned} |{\mathbb {T}}(G_0)|=m^{mn-2}\left( \prod _{u\in V(G)}(d_u(G)+1)^{m-1}\right) |{\mathbb {T}}(G)|. \end{aligned}$$

6.6 Generalized line graphs

Next we consider the number of spanning trees of generalized line graphs, which arose in the context of graph spectra. It is known that connected graphs with minimum eigenvalue at least $-2$ consist of line graphs, generalized line graphs and exceptional graphs (see [6, 12, 13]).

Fig. 2

Construction of a generalized line graph

We say that a petal is attached to a vertex u when we add a pendant edge at u and duplicate this edge to form a pendant 2-cycle. Let H be a simple undirected graph with vertex set $\{u_1,\ldots ,u_n\}$. Let ${\widehat{H}}=H(a_1,\ldots ,a_n)$ denote the multigraph obtained from H by attaching $a_i$ petals at $u_i$ ($i=1,\ldots ,n$). The generalized line graph [13, 35] $L({\widehat{H}})$ is defined as follows: The vertices of $L({\widehat{H}})$ are edges of ${\widehat{H}}$, and two vertices of $L({\widehat{H}})$ are adjacent whenever the corresponding edges in ${\widehat{H}}$ have exactly one common vertex. When $a_1=\cdots =a_n=0$, $L({\widehat{H}})$ is just the ordinary line graph ${\mathcal {L}}(H)$.

The following is an example of the construction of a generalized line graph, which is given in [13].

Example 6.27

[13] The graph H in Fig. 2 has vertex set $\{1,2,3,4\}$. The multigraph ${\widehat{H}}=H(1,0,0,2)$ is obtained from H by attaching one petal to vertex 1 and two petals to vertex 4. Then, $L({\widehat{H}})$ is a generalized line graph, and the intersection graph $\Omega ({\widehat{H}})$ is obtained from $L({\widehat{H}})$ by adding edges $\{a,b\},\{g,h\},\{i,j\}$. Vertices a and b are not adjacent in $L({\widehat{H}})$ because a and b have two common vertices in ${\widehat{H}}$. Vertices h and i are adjacent in $L({\widehat{H}})$ because h and i have exactly one common vertex in ${\widehat{H}}$.

Theorem 6.28

Let ${\widehat{H}}=H(a_1,\ldots ,a_n)$, where H is a connected graph with n vertices. Then,

$$\begin{aligned} |{\mathbb {T}}(L({\widehat{H}}))|=\prod _{i\in V(H)}b_i^{a_i-2}(b_i-2)^{a_i}\prod _{\{u,v\}\in E(H)}(b_u+b_v)\sum _{T\in {\mathbb {T}}(H)}\prod _{\{u,v\}\in E(T)}\frac{b_ub_v}{b_u+b_v}, \end{aligned}$$

where $b_i=d_i(H)+2a_i$.

Proof

Let $b_i=d_i(H)+2a_i$, $i=1,\ldots ,n$. For $u\in V({\widehat{H}})$ and $e\in E({\widehat{H}})$ incident to u, we assign the weight $w_{ue}$ to the edge $\{u,e\}$ in the incidence graph $I_{{\widehat{H}}}$ such that

$$\begin{aligned} w_{ue}={\left\{ \begin{array}{ll}b_u\qquad \qquad ~~~~&{}\text{ if }~u\in V(H),\\ -2\qquad \qquad ~~~&{}\text{ if }~u\in V({\widehat{H}}){\setminus } V(H).\end{array}\right. } \end{aligned}$$

Note that $L({\widehat{H}})$ has the same vertex set with the intersection graph $\Omega ({\widehat{H}})$, and the 2-section graph ${\widehat{H}}_{(2)}$ is obtained from ${\widehat{H}}$ by replacing each petal with a pendant edge. By Theorem 4.2, we have

$$\begin{aligned} t(I_{{\widehat{H}}},w)= & {} \prod _{i\in V({\widehat{H}})}\alpha _i \sum _{T\in {\mathbb {T}}(\Omega ({\widehat{H}}))}\prod _{\{e,f\}\in E(T)} \sum _{u\in e\cap f}\frac{w_{ue}w_{uf}}{\alpha _u}\\= & {} \prod _{e\in E({\widehat{H}})}\alpha _e\sum _{T\in {\mathbb {T}}({\widehat{H}}_{(2)})}\prod _{\{u,v\}\in E(T)}\sum _{\{u,v\}\subseteq e\in E({\widehat{H}})}\frac{w_{ue}w_{ve}}{\alpha _e}, \end{aligned}$$

where

$$\begin{aligned} \alpha _i= & {} \sum _{i\in f\in E({\widehat{H}})}w_{if}={\left\{ \begin{array}{ll}b_i^2\qquad \qquad ~~~~&{}\text{ if }~i\in V(H),\\ -4\qquad \qquad ~~~&{}\text{ if }~i\in V({\widehat{H}}){\setminus } V(H),\end{array}\right. }\\ \alpha _e= & {} \sum _{i\in V({\widehat{H}}),i\in e}w_{ie}={\left\{ \begin{array}{ll}b_u+b_v~~~~~~~~~&{}\text{ if }~e=\{u,v\}\in E(H),\\ b_u-2\qquad \qquad &{} \text{ if }~e=\{u,v\}\in E({\widehat{H}}),v\in V({\widehat{H}}){\setminus } V(H).\end{array}\right. } \end{aligned}$$

Then,

$$\begin{aligned} \prod _{i\in V({\widehat{H}})}\alpha _i=(-4)^{\sum _{i=1}^na_i}\prod _{i\in V(H)}b_i^2,~\prod _{e\in E({\widehat{H}})}\alpha _e=\prod _{i\in V(H)}(b_i-2)^{a_i}\prod _{\{u,v\}\in E(H)}(b_u+b_v), \end{aligned}$$

and

$$\begin{aligned} t(\Omega ({\widehat{H}}),w)(-4)^{\sum _{i=1}^na_i}\prod _{i\in V(H)}b_i^2=t({\widehat{H}}_{(2)},w)\prod _{i\in V(H)}(b_i-2)^{a_i}\prod _{\{u,v\}\in E(H)}(b_u+b_v), \end{aligned}$$

(6.5)

where $\Omega ({\widehat{H}})$ and ${\widehat{H}}_{(2)}$ have edge weights

$$\begin{aligned} w_{ef}(\Omega ({\widehat{H}}))=\sum _{u\in e\cap f}\frac{w_{ue}w_{uf}}{\alpha _u},~w_{uv}({\widehat{H}}_{(2)})=\sum _{\{u,v\}\subseteq e\in E({\widehat{H}})}\frac{w_{ue}w_{ve}}{\alpha _e}. \end{aligned}$$

For $\{e,f\}\in E(\Omega ({\widehat{H}}))$, we have

$$\begin{aligned} \sum _{u\in e\cap f}\frac{w_{ue}w_{uf}}{\alpha _u}={\left\{ \begin{array}{ll}1\qquad \qquad ~~~&{}\text{ if }~|e\cap f|=1,\\ 0\qquad \qquad ~~~&{}\text{ if }~|e\cap f|=2.\end{array}\right. } \end{aligned}$$

Hence,

$$\begin{aligned} t(\Omega ({\widehat{H}}),w)=|{\mathbb {T}}(L({\widehat{H}}))|. \end{aligned}$$

(6.6)

For $\{u,v\}\in E({\widehat{H}}_{(2)})$, we have

$$\begin{aligned} \sum _{\{u,v\}\subseteq e\in E({\widehat{H}})}\frac{w_{ue}w_{ve}}{\alpha _e}={\left\{ \begin{array}{ll}\frac{b_ub_v}{b_u+b_v}~~~~~~~~~&{}\text{ if }~e=\{u,v\}\in E(H),\\ \frac{-4b_u}{b_u-2}\qquad \qquad &{} \text{ if }~e=\{u,v\}\in E({\widehat{H}}),v\in V({\widehat{H}}){\setminus } V(H).\end{array}\right. } \end{aligned}$$

If $e=\{u,v\}\in E({\widehat{H}})$ and $v\in V({\widehat{H}}){\setminus } V(H)$, then e is a pendant edge in ${\widehat{H}}_{(2)}$. So each spanning tree of ${\widehat{H}}_{(2)}$ is obtained from a spanning tree of G by adding $\sum _{i=1}^na_i$ pendant edges. Hence,

$$\begin{aligned} t({\widehat{H}}_{(2)},w)=\prod _{i\in V(G)}\left( \frac{-4b_i}{b_i-2}\right) ^{a_i}\sum _{T\in {\mathbb {T}}(H)}\prod _{\{u,v\}\in E(T)}\frac{b_ub_v}{b_u+b_v}. \end{aligned}$$

(6.7)

The formula of $|{\mathbb {T}}(L({\widehat{H}}))|$ follows from Eqs. (6.5)–(6.7). $\square$

Theorem 6.28 yields the following formula.

Corollary 6.29

Let ${\widehat{H}}=H(a_1,\ldots ,a_n)$, where H is a connected graph with n vertices and m edges. If $d_i(H)+2a_i=b$ for some nonnegative integers $a_1,\ldots ,a_n$, then

$$\begin{aligned} |{\mathbb {T}}(L({\widehat{H}}))|=2^{m-n+1}b^{m-n-1+a}(b-2)^a|{\mathbb {T}}(H)|, \end{aligned}$$

where $a=a_1+\cdots +a_n$.

6.7 Oriented spanning trees in vertex-weighted graphs

Let G be a vertex-weighted graph on n vertices, and each vertex $u\in V(G)$ is weighted by an indeterminate $w_u(G)$. For a vertex v in a spanning tree T of G, let $T_v$ denote the rooted directed tree obtained by orienting every edge of T toward the root v, and let $E(T_v)$ denote the set of directed edges of $T_v$. The weight of $T_v$ is defined as $w(T_v)=\prod _{\overrightarrow{ij}\in E(T_v)}w_j(G)$, where $\overrightarrow{ij}$ means that there is a directed edge from i to j. A polynomial on oriented spanning trees is defined as [9]

$$\begin{aligned} \kappa (G,w)=\sum _{v\in V(G)}\sum _{T\in {\mathbb {T}}(G)}w(T_v). \end{aligned}$$

If $w_u(G)=1$ for each $u\in V(G)$, then $\kappa (G,w)=n|{\mathbb {T}}(G)|$ is the number of oriented spanning trees of G.

The vertex-weighted Laplacian [9] ${\mathbb {L}}_G$ is the $n\times n$ symmetric matrix with entries

$$\begin{aligned} ({\mathbb {L}}_G)_{ij}={\left\{ \begin{array}{ll}\sum _{\{i,k\}\in E(G)}w_{k}(G)\qquad \qquad &{} \text{ if }~i=j,\\ -w_i(G)^{\frac{1}{2}}w_j(G)^{\frac{1}{2}}\qquad \qquad \; &{}\text{ if }~\{i,j\}\in E(G),\\ 0\qquad \qquad \qquad \qquad \qquad \qquad \quad &{}\text{ otherwise }.\end{array}\right. } \end{aligned}$$

The following is the matrix-tree theorem for vertex-weighted graphs.

Lemma 6.30

[9] Let G be a weighted graph on n vertices, and each vertex $u\in V(G)$ is weighted by an indeterminate $w_u(G)$. For any $i,j\in \{1,\ldots ,n\}$, let ${\mathbb {L}}_G(i,j)$ be the submatrix of ${\mathbb {L}}_G$ obtained by deleting the ith row and the jth column. Then,

$$\begin{aligned} w_i(G)^{\frac{1}{2}}w_j(G)^{\frac{1}{2}}\left( \sum _{u\in V(G)}w_u(G)\right) ^{-1}\kappa (G,w)=(-1)^{i+j}\det ({\mathbb {L}}_G(i,j)). \end{aligned}$$

The following is the relation between the polynomials $\kappa (G,w)$ and t(G, w).

Lemma 6.31

Let G be a weighted graph on n vertices. If each vertex $u\in V(G)$ is weighted by an indeterminate $w_u(G)$ and each edge $\{i,j\}\in E(G)$ is weighted by an indeterminate $w_i(G)w_j(G)$, then

$$\begin{aligned} \kappa (G,w)\prod _{u\in V(G)}w_u(G)=t(G,w)\sum _{u\in V(G)}w_u(G). \end{aligned}$$

Proof

Let $W=\mathrm{diag}(w_1(G),\ldots ,w_n(G))$ be the diagonal matrix of vertex weights of G. Then, $L_G=W^{\frac{1}{2}}{\mathbb {L}}_GW^{\frac{1}{2}}$. By Lemmas 2.4 and 6.30 , we have $\kappa (G,w)\prod _{u\in V(G)}w_u(G)=t(G,w)\sum _{u\in V(G)}w_u(G)$. $\square$

By Lemma 6.31 and Theorem 5.1, we derive the following clique partition formula for counting oriented spanning trees in a vertex-weighted graph.

Theorem 6.32

Let G be a vertex-weighted graph, and each vertex $u\in V(G)$ is weighted by an indeterminate $w_u$. For a clique partition $\varepsilon =\{Q_1,\ldots ,Q_r\}$ of G, we have

$$\begin{aligned} \kappa (G,w)= & {} \frac{\sum _{u\in V(G)}w_u\prod _{u\in V(G)}(\sum _{Q_i\in S_u}d_{Q_i})}{\prod _{i=1}^rd_{Q_i}^2}\\&\quad \times \sum _{T\in {\mathbb {T}}(\Omega (\varepsilon ))}\prod _{\{Q_i,Q_j\}\in E(T)}\frac{d_{Q_i}d_{Q_j}w_{\kappa (Q_i,Q_j)}}{\sum _{Q_u\in S_{\kappa (Q_i,Q_j)}}d_{Q_u}}, \end{aligned}$$

where $d_{Q_i}=\sum _{u\in Q_i}w_u$ and $\kappa (Q_i,Q_j)\in Q_i\cap Q_j$ is the unique common vertex of $Q_i$ and $Q_j$.

7 Concluding remarks

In this paper, we introduce the Schur complement formula and local transformation formula of t(G, w) and use these formulas to obtain expressions for enumerating spanning trees in a graph G via its intersection representations and clique partitions. The local transformation formula is a special case of the Schur complement formula. Some formulas in Sects. 3–5 are useful for the enumeration of spanning trees in a general graph, not only the families of graphs mentioned in Sect. 6.

On the one hand, we can express t(G, w) in terms of smaller Schur complement weighted graphs. On the other hand, the Schur complement formula reveals the internal connection between spanning trees of two Schur complement weighted graphs (cf. Proposition 3.1 and 3.3). For example, in Theorem 4.2, $\Omega (H)$ and $H_{(2)}$ are just two Schur complement weighted graphs of $I_H$, so we can obtain the relation between spanning trees of $\Omega (H)$ and $H_{(2)}$ and derive the clique partition formula in Sect. 5.