On the number of spanning trees in graphs with multiple edges

Abstract

In order to solve a problem, a usual approach is to represent it in a simple structure and bring it to some particular cases. In graph theory, this approach is used to illustrate this problem by a graph, then treat it on simple sets expressing the relations between its elements. Thus that researchers saw the appearance of spanning trees. The aim of this approach is the evaluation of the number of spanning trees in some networks which can not be find using the existing methods, such as large networks, or with multiple connections. In this paper we focus on graphs with multiple edges and we consider the multi-edges fan and wheel graphs, deriving of exact and recursive functions based on operations and geometric transformations.

1 Introduction

Enumeration of spanning trees of a graph has been the subject of several Studies in the history of mathematics. However, this area is still a very active field of research since that the number of spanning trees was the interest of several researchers in different disciplines. This number is an important invariant related to different topological and dynamical properties of graphs, such as its reliability for communication networks [1–3], robustness for social networks [4, 5], synchronization capability [6] and the study of random walks [7].

The number of spanning trees of a graph that describes a network tends to be one of the most natural characteristics from the viewpoint of its reliability, and deriving a formula to count the number of spanning trees for various graphs has become a vital role not only in applied mathematics but also in computer science.

Indeed, the graph theory ensures a good modeling of a communication network such as the vertices of graph represent the nodes of the network and edges illustrate the interconnection between nodes.

In this paper, we assume that $G = (V_{G},E_{G},F_{G})$ is a planar connected graph with $V_{G}$ is the set of vertices, $E_{G}$ is the set of edges and $F_{G}$ is the set of faces.

In the topological sense, a graph is said to be connected if each pair of its vertices belongs to a path, while the planarity constraint is verified when no edges are crossing each other. We define a tree as a connected graph without cycle and a spanning tree of G, a subgraph of G that includes every vertex and is also a tree [8].

The number of spanning trees of a graph, also called it’s complexity, is the set of all the spanning trees of this graph noted $\tau (G)$. The study of this number was initiated by the physicist Kirchoff who proposed the called “Matrix Tree Theorem” expressing the number of spanning tree for any graph by determined the Laplacian matrix defined by $L(G)=D(G)-A(G)$, with D(G) and A(G) are respectively the matrix of degrees and the adjacency matrix [9]. The advantage of this theorem resides in the fact that it processes any type of graph. However, for large graphs, with a large number of vertices, the use of this result become impractical due to the calculation of the determinant of a large matrix. The remedy to this problem was to develop a simple technique to enumerate spanning trees of a graph without going through the determinant. Thus, Cayley proposed a great expression for the number of spanning trees in complete graphs $K_{n}$ on n vertices, $K_{n}$ graph has $n^{n-2}$ spanning trees [10]. Then Feussner [11] managed to find a technical based on simple operations (deletion and contraction), which consists in establishing recursive functions computing the complexity of planar graphs without passing through the laplace of the latter. According to Feussner, let G be a planar graph, for any edge $e=uv \in E_{G}$

$$\begin{aligned} \tau (G) = \tau (G-e) + \tau (G\cdot e) \end{aligned}$$

(1)

However, the only disadvantage of this method is that its use concerns only graphs containing a single edge, Thus we propose its generalization to treat graphs with multiple edges. The enumeration of spanning trees for large graphs with infinite vertices is a demanding and a difficult task, thus there is much interest in obtaining closed expressions. Wherefore, many works derive formulas to calculate the complexity for some classes of simple graphs (without loops or multiple edges) [12–19]. Bogdanowicz [13], Myers [20] and Haghighi [15] derives the explicit formulas $\tau (F_{n})$ and $\tau (W_{n})$; the number of spanning trees in Fan and Wheel graphs with ($n= |V_{F_{n}}|-2$) to be (Fig. 1):

$$\begin{aligned} \tau (F_{n})= & {} \frac{1}{\sqrt{5}}\left( \left( \frac{3+\sqrt{5}}{2}\right) ^n-\left( \frac{3-\sqrt{5}}{2}\right) ^n \right) \end{aligned}$$

(2)

$$\begin{aligned} \tau (W_{n})= & {} \frac{1}{\sqrt{5}}\left( \left( \frac{3+\sqrt{5}}{2}\right) ^n-\left( \frac{3-\sqrt{5}}{2}\right) ^n-2\right) \end{aligned}$$

(3)

Fig. 1

The fan and wheel graphs

Previous researches on techniques facilitating the enumeration of spanning trees treat simple graphs. Although many problem in practice can be represented by graphs. Consider the example of wide communication networks where the number of spanning trees is an important measure of the reliability, and that of social networks where it represents the network robustness, this invariant may be investigated to study the reliability and robustness respectively of communications and social networks. These kind of networks are characterized by multiple connections between its components, that problem was not treated before, whence the interest of our paper to treat graphs with multiple connections.

In the following, we deal with non simple graphs that contains multiple edges (loops do not contribute on the construction of a spanning tree). We describe a general formula based on deletion contraction of multiple edges, we focus on the planar k-multi-edges graphs $F_{n,k}$ and $W_{n,k}$ illustrated in Fig. 2, with n the number of sets of multiple edges and k the number of edges in a set of multiple edges. The $F_{n,k}$ graph represented at the left of the Fig. 2 contains $n+1$ vertices, n faces and $n\cdot (k+1)-1$ edges with one complete vertex of degree $n\cdot k$ connected to each vertex by k multi-edges, two vertices of degree $k+1$ and the rest of degree $k+2$, and at the right is illustrated the $W_{n,k}$ graph on $n+1$ vertices, $n+1$ faces and $n.(k+1)$ edges which is formed from a cycle $C_{n-1}$ on $n-1$ vertices by adding a vertex adjacent to every vertex of $C_{n-1}$ (complete vertex) by k multiple edges, the complete vertex is of degree n.k and the rest of $k+2$ degree.

Fig. 2

The k-multi-edges fan and wheel graphs

The rest of the paper is organized as follows. Section 2 describes a generalization of feussner’s formula to treat non simple graphs with multiple edges, Sect. 3 describes the application of this generalization to count spanning trees in fan graphs with multiple edges. Section 4 treat complexity of the multi-edges wheel graph. Finally, Sect. 5 concludes the paper.

2 Spanning trees in graphs with multiple edges

Previous works in computing spanning trees found formulas that enumerate spanning trees in simple graphs (without loops or multiple edges). In this section we present our research result, a formula seen as a generalization of Feussner’s technical to treat graphs with multiple edges. Then, we apply it in Sect. 3 to find exact and recursive formulas to compute complexities of two famous graphs, the fan and wheel graphs by more feature; that of the multiple edges.

Definition 2.1

Let G be a graph and let u, v be two vertices of G connected by multiple edges $e_{k}$. We denote by $G - e_{k}$ the graph obtained by deleting the multiple edges $e_{k}$ and the graph remains connected, and by $G\cdot e_{k}$ or G.uv the graph obtained by deleting the multiple edges $e_{k}$ and pasting the two vertices u and v.

Here is an example of graphs G, $G-e_{k}$ and $G\cdot e_{k}$; see Fig. 3.

Fig. 3

$G,\ G-e_{k}\ \mathrm{and}\ G\cdot uv$

Lemma 2.2

Let G be a graph If $e_{k} = uv \in E(G)$ ($e_{k}$ are multiple edges $e_{1},e_{2},\ldots ,e_{k}$); see Fig. 3, then:

$$ \tau (G)=\tau (G-e_{k})+k\cdot \tau (G.uv)$$

Proof

Let S be the set of spanning trees of a graph G;

$\tau (G)=|S|$

$S_{1}$ is the set of spanning trees of G without the multiple edges $e_{k}$;

$|S_{1}|=\tau (G-e_{k})$

$S_{2}$ is the set of spanning trees of G containing the multiple edges $e_{k}$;

$|S_{2}|=k\cdot \tau (G\cdot e_{k})$ since we have k multiple edges to delete

$|S|=|S_{1}|+|S_{2}|$, then $\tau (G)=\tau (G-e_{k})+k\cdot \tau (G\cdot uv)$.

3 Complexity of fan graph with multiple edges

In this section we enumerate spanning trees of the fan graph with multiple edges, we consider the regular k-multi-edges fan illustrated in the left of Fig. 2 denoted $F_{n,k}$, we found exact and recursive formulas to compute its complexity, afterwards we compute that of the ($k',k$)-multi-edges fan illustrated in Fig. 5 which will be used to compute the complexity of the k-multi-edges wheel graph (see Sect. 4).

3.1 The regular k-multi-edges fan graph

Let $F_{n,k}$ be the fan graph with k multiple edges, and let $C_{n,k}$ represent its complexity (Fig. 4).

Fig. 4

Family of k-multi-edges fan graphs: $F_{0}$, $F_{1,k}$, $F_{2,k}$, $F_{3,k}$, $\ldots$ ,$F_{n,k}$

Lemma 3.1

The number of spanning trees in the planar k-multi-fan is defined as the sequence:

$$\begin{aligned} \left\{ \begin{array}{l} C_{n,k} = k\sum _{i=0}^{n-1}C_{i,k}+C_{n-1,k} \\ C_{0,k} = 1 \\ C_{1,k} = k \\ \end{array} \right. \end{aligned}$$

Proof

$$\begin{aligned} C_{0,k}= & {} 1\\ C_{1,k}= & {} k \end{aligned}$$

we apply the Lemma 2.2 recursively until get:

$$\begin{aligned}&C_{2,k}=C_{1,k}+k.C_{1,k+1}\\&C_{3,k}=(1+k)C_{1,k}+C_{2,k}\cdot C_{1,k+1}\\&C_{4,k}=(1+k+C_{2,k})C_{1,k})+C_{3,k}\cdot C_{1,k+1}\\&C_{5,k}=(1+k+C_{2,k}+C_{3,k})C_{1,k}+C_{4,k}\cdot C_{1,k+1}\\&\vdots \\&C_{n,k}=(1+k+C_{2,k}+C_{3,k}+\cdots + C_{n-2,k})C_{1,k}+C_{n-1,k}\cdot C_{1,k+1} \end{aligned}$$

with $C_{1,k+1}=k+1$, then the result.

The latest works in graph theory are often performed by computer scientists, because of the importance that assume the algorithmic aspects.

We can compute the complexity of $F_{n,k}$ otherwise as an applicative way, by the derivation of the following simple recursive formula:

Lemma 3.2

Spanning trees of $F_{n,k}$ satisfies:

$$\begin{aligned} C_{n,k}=(k+2)C_{n-1,k}-C_{n-2,k}, \ n \ge 2 \end{aligned}$$

Proof

then the result.

It is desired to establish a functional expression of the complexity of sequence, in other words an expression such as computing the number of pairs for a given values of n and k does not presuppose the knowledge of any number of pairs for any else values n and k, which does not enable the recurrence formula.

Theorem 3.3

Complexity of the k-multi-fan graph is given by the following formula depending on n and k

$$\begin{aligned} C_{n,k}=\frac{k}{\sqrt{k^2+4k}}\left( \left( \frac{k+2+\sqrt{k^2+4k}}{2}\right) ^n-\left( \frac{k+2-\sqrt{k^2+4k}}{2}\right) ^n \right) ,\quad \ n\ge 2 \end{aligned}$$

Proof

We consider the formula in Lemma 3.1 as:

$$\begin{aligned} \left\{ \begin{array}{l} U_{n}=k(U_{0}+U_{1}+\cdots +U_{n-1})+U_{n-1} \\ U_{0} = 1 \\ U_{1} = k \\ \end{array} \right. \end{aligned}$$

We pose $S_{n}=U_{0}+U_{1}+\cdots +U_{n-1}+U_{n}$, so $U_{n}=S_{n}-S_{n-1}$ that we inject in the equation;

$$\begin{aligned} \left\{ \begin{array}{l} S_{n}-S_{n-1}=k.S_{n-1}+S_{n-1}-S_{n-2}\\ S_{0} = 1\\ S_{1} = k+1\\ \end{array} \right. \qquad \Rightarrow \qquad \left\{ \begin{array}{l} S_{n}=(k+2)S_{n-1}-S_{n-2}\\ \beta =\frac{1+k-r_{1}}{r_{2}-r_{1}}\\ \end{array} \right. \end{aligned}$$

The characteristic equation is $r^2-(k+2)r+1=0$, $\Delta =k^2+4k > 0$ therefore, the solutions of this equation are: $r_{1}=\frac{k+2-\sqrt{k^2+2k}}{2}$ and $r_{2}=\frac{k+2+\sqrt{k^2+2k}}{2}$, hence

$$\begin{aligned} S_{n}=\alpha \cdot r_{1}^n+\beta \cdot r_{2}^n , \quad \alpha ,\beta \in R, n\ge 0 . \end{aligned}$$

$U_{n}=S_{n}-S_{n-1}=\alpha \cdot r_{1}^{n-1}(r_{1}-1)+\beta \cdot r_{2}^{n-1}(r_{2}-1)$, using the initial conditions

$$\begin{aligned} \left\{ \begin{array}{l} \alpha +\beta =1\\ \alpha .r_{1}+\beta \cdot r_{2} = 1+k\\ \end{array} \right. \qquad \Rightarrow \qquad \left\{ \begin{array}{l} \alpha =\frac{r_{2}-1-k}{r_{2}-r_{1}}\\ \beta =\frac{1+k-r_{1}}{r_{2}-r_{1}}\\ \end{array} \right. \end{aligned}$$

we replace in the equation and develop to get:

$$\begin{aligned} U_{n}= & {} \frac{1}{r_{2}-r_{1}}\left( (r_{2}-1)^2\cdot r_{2}^{n-1}-(r_{1}-1)^2\cdot r_{1}^{n-1}\right) \\ U_{n}= & {} \frac{1}{\sqrt{k^2+4k}}\left( \left( \frac{k+\sqrt{k^2+2k}}{2}\right) ^2\left( \frac{k+2+\sqrt{k^2+2k}}{2}\right) ^{n-1}\right. \\&\left. -\,\left( \frac{k-\sqrt{k^2+2k}}{2}\right) ^2\left( \frac{k+2-\sqrt{k^2+2k}}{2}\right) ^{n-1}\right) , \end{aligned}$$

hence the result.

Particular case In the previous Theorem 3.3, if we take $k = 1$, we obtain formula of the simple fan graph $F_{n}$ mentioned in Eq. (1).

3.2 The (k$^{\prime }$,k)-multi-edges fan graph

In this subsection we focus on the enumeration of spanning trees in the $(k',k)$-multi-edges fan graph, denoted by $F_{n,k',k}$, with n number of triangles, $k'\in \mathbb {N}$ the degree of the first multiple edges and the rest are k degrees as shown in Fig. 5, the complexity of this graph will be needed to compute that of the k-multi-edges wheel graph $W_{n,k}$ treated in Sect. 4.

Fig. 5

the $(k',k)$ multi-edges fan $F_{n,k',k}$

Lemma 3.4

Spanning trees in the planar $(k',k)$ multi-fan graph denoted $C_{n,k',k}$ are computed as:

$$\begin{aligned} C_{n,k',k}=k\sum _{i=0}^{n-2}C_{i,k}+k'\sum _{i=1}^{n-2}C_{i,k}(k+1)^{n-i-2}+C_{n-2,k}+k'(k+1)^{n-1},\quad \ n\ge 2 \end{aligned}$$

Proof

Using Lemma 2.2 we have:

$$\begin{aligned} C_{n,k',k}=C_{n-1,k}+k'\cdot C_{n-1,k+1,k} \end{aligned}$$

To compute spanning trees of $F_{n,k',k}$ we need to compute that of $F_{n,k+1,k}$, we reuse Lemma 2.2 recursively:

$$\begin{aligned}&C_{n,k+1,k} = C_{n-1,k}+(k+1)\times C_{n-1,k+1,k}\\&C_{n-1,k+1,k} = C_{n-2,k}+(k+1) \times C_{n-2,k+1,k}\\&C_{n-2,k+1,k} = C_{n-3,k}+(k+1)\times C_{n-3,k+1,k}\\&C_{n-3,k+1,k} = C_{n-4,k}+(k+1)\times C_{n-4,k+1,k}\\&\vdots \\&C_{3,k+1,k} = C_{2,k}+(k+1)\times C_{2,k+1,k}\\&C_{2,k+1,k} = C_{1,k}+(k+1)\times C_{1,k+1,k} \end{aligned}$$

with $C_{1,k+1,k}=C_{k+1}=k+1.$

We multiply the equation of $C_{n-1,k+1,k}$ by $(k+1)$, the equation of $C_{n-2,k+1,k}$ by $(k+1)^2$ and so on until the last equation $C_{2,k+1,k}$ which will be multiplied by $(k+1)^{n-2}$. Summing all the obtained equations, we can find the number of spanning trees in $C_{n,k+1,k}$ which is given by: $C_{n,k+1,k}=\sum _{i=1}^{n-1}C_{i,k}.(k+1)^{n-i-1}+(k+1)^{n},\ n\ge 2$ we replace this result and that found in Lemma 3.1 in Lemma 3.4; to obtain $C_{n,k',k}$ the complexity of $F_{n,k',k}$.

The Fig. 6 illustrate an example of computation of $C_{4,k+1,k}$:

Fig. 6

Complexity of $F_{4,k+1,k}$

4 Complexity of the multi-edges wheel graph

Let $W_{n,k}$ be the k-multi-edges wheel graph represented in the right of Fig. 2 and let $A_{n,k}$ represent its number of spanning trees $\tau (W_{n,k})=A_{n,k}$

Theorem 4.1

Complexity of the k-multi-wheel graph is given by the following formula depending on n and k

$$\begin{aligned} A_{n,k}=\sum _{i=1}^{n}C_{i,(n-i+1)k,k} \end{aligned}$$

Proof

We use deletion contraction method recursively for $W_{n,k}$ (as illustrated in the example of Fig. 7, for $n=4$), to compute $A_{n,k}$ as follow:

$$\begin{aligned}&A_{n,k}=C_{n,k}+A_{n-1,2k,k}\\&A_{n-1,2k,k}=C_{n-1,2k,k}+A_{n-2,3k,k}\\&A_{n-2,3k,k}=C_{n-2,3k,k}+A_{n-3,4k,k}\\&A_{n-3,4k,k}=C_{n-3,4k,k}+A_{n-4,5k,k}\\&\vdots \\&A_{2,(n-1)k,k}=C_{2,(n-1)k,k}+n.k \end{aligned}$$

with $C_{1,nk,k}=C_{1,nk}=n.k$, we sum previous equations to obtain the result.

The Fig. 7 bellow explains the demo, we fix $n=4$ and compute $A_{4,k}$

Fig. 7

Complexity of $A_{4,k}$

5 Conclusion

Previous works in computation of spanning trees in planar graphs treat simple undirected graphs with no loops or multiple edges. In this paper, we have interested by enumerating spanning trees in undirected graphs with multiple edges, we have considered a special kinds of graphs with multiple connections called the k-multi-edges fan and wheel graphs, $F_{n,k}$ and $W_{n,k}$, with k the number of multiples edges. We considered the deletion contraction technique of multiple edges, for these latter we found exact and recursive formulas that express complexity of those graphs, and which can be used for both simple and multiple edges graphs.