Tutte polynomial of self-similar network models with applications

Aboutahoun, A.; El-Safty, F.

doi:10.61091/ars157-05

Abstract

1. Introduction
2. Preliminaries
3. Tutte polynomial of M(t)
4. Applications
5. Conclusion
Declarations
Conflict of Interest

References

Ars Combinatoria

Volume 157
Pages: 53-63

Research article

Tutte polynomial of self-similar network models with applications

^¹,², ^³

¹Zewail City of Science and Technology, $6^{\textrm{th}}$ of October City, Giza, Egypt.

²Department of Mathematics, Faculty of Science, Alexandria University, Egypt.

³Faculty of Science, Damanhour University, Damanhour, Egypt.

Received: 17/09/2023
Accepted: 01/12/2023
Published: 03/12/2023

Copyright Link
License

Abstract

Determining the Tutte polynomial $T (G; x, y)$ of a graph network $G$ is a challenging problem for mathematicians, physicians, and statisticians. This paper investigates a self-similar network model $M (t)$ and derives its Tutte polynomial. In addition, we evaluate exact explicit formulas for the number of acyclic orientations and spanning trees of it as applications of the Tutte polynomial. Finally, we use the derived $T (M (t); x, y)$ to obtain the Tutte polynomial of another self-similar model $N (t)$ presented in [1] and correct the main result discussed in [1] by Ma et al. and test our result numerically by using Matlab.

1. Introduction

The Tutte polynomial is a graph polynomial that encodes a variety of combinatorial and algebraic information about the graph. It was first studied by William Tutte[2,3] in 1954 and known as the dichromatic polynomial since it is a generalization of the chromatic polynomials introduced by Birkoff[4] and Whitney[5]. The Tutte polynomial is a well-known tool for examining the characteristics and properties of graphs [6]. The university of the Tutte polynomial is derived from the recipe theorem (see [7, 8]). The crucial universal property of this graph polynomial is that practically every multiplicative graph invariant with a deletion/contraction reduction must be an evaluation of it[9]. These deletion/contraction operations are natural reductions for many network models arising from a variety of problems at the computer science, engineering, statistics, optimization, and physics.
The Tutte polynomial $T (G; x, y)$ of a graph $G = (V, E)$ is a polynomial in two variables $x$ and $y$ . Numerous of graph polynomials are specially obtained from the Tutte polynomial. For example, the chromatic polynomial $P (G; x)$ of $G$ is a one-variable graph invariant counts the number of distinct ways to colour $G$ with $x$ colours. The Tutte polynomial includes the chromatic polynomial as a specialization[10, 11, 12]: $P (G; x) = (- 1)^{| V | - k (G)} x^{k (G)} T (G; 1 - x, 0),$ where $k (G)$ is the number of the connected components of $G$ .
Also, the flow polynomial $F (G; y)$ that counts the number of flows in $G$ can be derived from the Tutte polynomial as follows[2]: $F (G; y) = (- 1)^{| E | - | V | + k (G)} T (G; 0, 1 - y)$ Furthermore, the reliability polynomial $R (G; y)$ of $G$ is a graph polynomial that measures the probability that no connected component of $G$ is disconnected when an edge of $G$ with fixed probability $0 \leq y \leq 1$ , is independently deleted. The reliability polynomial is also a special polynomial due to the Tutte polynomial [13]: $R (G; y) = y^{| V | - 1} (1 - y)^{| E | - | V | + 1} T (G; 1, \frac{1}{1 - y})$ The Tutte polynomials can be defined for graphs, matrices, and matroids. We concern with finding the Tutte polynomial for a class of self-similar network. Focusing on self-similar networks arises from being able to represent some real networks. Networks with self-similarity property have been studied in various fields, such as mathematics, computer science, physics, chemistry, and biology (see[14,15,16,17,18]). There are diverse and different examples of this networks such as Von Koch graphs, Sierpinski gasket graphs, and tower of Hanoi graphs (see [19, 20]). Therefore, calculating the Tutte polynomial for this kind of networks is of a great interest for many researchers ([24,25,26]).
The Tutte polynomial has evaluations that count a large number of the graph invariants. The number of acyclic orientation of a graph is a vital quantity that has many applications in different areas such as network optimization, social sciences and other fields. For example, the number of acyclic orientations of a scheduling network equals to the number of feedback arc set and the number of acyclic orientations of a social network measures its degree of hierarchy. Also, the number of acyclic orientations of a network measures its planarity. The number of acyclic orientations of a graph can be evaluated from the Tutte polynomial.
Another significant graph invariant is the number of spanning trees that is related to its structural and dynamical properties. The number of spanning trees of a self-similar network provides us with information about the effectiveness of the underlying network. It is well-known that the number of spanning trees of a graph equals to the determinant of any cofactor of the Laplacian matrix of the graph. For a graph with a huge number of nodes, finding analytically the number of spanning trees becomes harder and harsher. We overcome this difficulty by the aid of the Tutte polynomial which can enumerate it. Hence, evaluating the number of spanning trees of a network is considered as a crucial and fundamental application of the Tutte polynomials.
This paper is organized as follows. In Section 2, we introduce some definitions and results from graph theory that would be used throughout the paper and investigate a class of self-similar network model $M (t)$ . In Section 3, we study the Tutte polynomial $T (M (t); x, y)$ . Though determining the Tutte polynomial of a graph is generally an NP-hard problem, we shall find a recursive formula for the Tutte polynomial of a network model $M (t)$ based on the subgraph decomposition method [21,27,28]. Section 4 is devoted to the applications of $T (M (t); x, y)$ . We find the exact formula of the number of acyclic orientations and spanning trees of network model $M (t)$ . We also discuss the spanning tree entropy or the asymptotic complexity of $M (t)$ . In section 4, we examine the self-similar network $N (t)$ presented in [1] as another application of the underlying model $M (t)$ . We deduce the Tutte polynomial of $N (t)$ by applying some results published in[29]. The number of spanning trees of $N (t)$ is explicitly derived and coincided with the results obtained by using Matlab code which enhances the validity of them. Finally, Section 5 gives a brief summary.

2. Preliminaries

This section briefly presents some necessary definitions that will be used in our calculations. Let $G = (V (G), E (G))$ be a graph with node set $V (G)$ and edge set $E (G)$ . The order and size of $G$ are $| V (G) |$ and $| E (G) |$ , respectively. A subgraph $A = (V (A), E (A))$ of $G$ is called a spanning subgraph of $G$ if $A$ is obtained by edge deletion only, that is, $V (A) = V (G)$ and $E (A) \subseteq E (G)$ .

2.1. Tutte polynomial

The Tutte polynomial is a well-studied invariant of graphs. (For more details, see[11,23]). There are some different but still equivalent definitions of tutte polynomial[8]. Here we introduce the common subgraph extension definition. Let $A$ be a spanning subgraph of $G$ , then the Tutte polynomial $T (G; x, y)$ of $G$ is defined by

$\begin{matrix} (1) & T (G; x, y) = \sum_{A \subseteq G} (x - 1)^{k (A) - k (G)} (y - 1)^{| E (A) | - | V (A) | + k (A)}, \end{matrix}$ where the summation runs over all possible spanning subgraphs $A$ of $G$ and $k (A)$ is the number of connected components of $A$ . From $1$ ), we notice that theTutte polynomial of $G$ is a two-variable polynomial in $x$ and $y$ . It is remarkable that calculating the Tutte polynomial $T (G; x, y)$ of $G$ at particular points gives us distinctive combinatorial invariants of $G$ such that

$T (G; 1, 1) = τ (G)$ is the number of the spanning trees of $G$ .
$T (G; 2, 1) = F (G)$ is the number of the spanning forest of $G$ .
$T (G; 1, 2) = S (G)$ is the number of the spanning connected subgraphs of $G$ .
$T (G; 2, 2) = 2^{| E (G) |}$ .
$T (G; 2, 0) = a (G)$ is the number of acyclic orientations of $G$ .
$T (G; 0, 2) = t a (G)$ is the number of totally acyclic orientations of $G$ .

2.2. Proposed network model $M (t)$

The network model $M (t)$ can be constructed by an iterative method based on a merging process. The merging process could happen in the following manner.

At any time step $t$ , $M (t)$ has two special nodes $a_{t}$ and $b_{t}$ which are the nodes of the highest degree and an edge $e_{t}$ connecting them.
$M (t + 1)$ is obtained by merging 6 copies of $M (t)$ by joining their special nodes. Merging $a_{t}$ and $a_{t}$ gives a new special node $a_{t + 1}$ of $M (t + 1)$ and merging $b_{t}$ and $b_{t}$ gives a new special node $b_{t + 1}$ of $M (t + 1)$ . The two special nodes $a_{t + 1}$ and $b_{t + 1}$ of $M (t + 1)$ would be linked by a new edge $e_{t + 1}$ . The construction process of $M (t + 1)$ is illustrated in Figure 1.

Figure 1. Construction of network model $M (t + 1)$

For $t = 0$ , let $M (0)$ be a path with length one whose two endpoints are the special nodes $a_{0}$ and $b_{0}$ . For $t \geq 0$ , $M (t + 1)$ can be obtained from $M (t)$ by the construction process presented above, see Figure 2.

Figure 2. The diagrams of network model $M (t)$ at $t = 0, 1, 2$ .

After $t$ time steps, the order and size of $M (t)$ are, respectively, $\begin{aligned} (2) & | V (M (t)) | = \frac{4}{5} 6^{t} + \frac{6}{5} \\ (3) & | E (M (t)) | = \frac{1}{5} (6^{t + 1} - 1) \end{aligned}$ The solution of average degree of model $M (t)$ is $\begin{matrix} (4) & < k (M (t)) > = \frac{2 | E (M (t)) |}{| V (M (t)) |} = \frac{\frac{2}{5} (6^{t + 1} - 1)}{\frac{4}{5} 6^{t} + \frac{6}{5}} \approx 3. \end{matrix}$

3. Tutte polynomial of $M (t)$

The Tutte polynomial of the network model $M (t)$ is given by $\begin{matrix} (5) & T (M (t); x, y) = \sum_{A \subseteq M (t)} (x - 1)^{k (A) - 1} (y - 1)^{| E (A) | - | V (A) | + k (A)} \end{matrix}$ Let us categorize the spanning subgraphs $A$ of $M (t)$ into two kinds. The first kind $M (1, t)$ is the spanning subgraphs of $M (t)$ , where the two special nodes $a_{t}$ and $b_{t}$ belong to the same connected component. The second kind $M (2, t)$ is the spanning subgraphs of $M (t)$ , where the two special nodes $a_{t}$ and $b_{t}$ belong to two different connected components.
Hence, equation ( $5$ ) can be rewritten as $\begin{matrix} (6) & T (M (t); x, y) = T_{1, t} (x, y) + T_{2, t} (x, y), \end{matrix}$ where $\begin{aligned} (7) & T_{1, t} (x, y) = \sum_{A \subseteq M (1, t)} (x - 1)^{k (A) - 1} (y - 1)^{| E (A) | - | V (A) | + k (A)} \\ (8) & T_{2, t} (x, y) = \sum_{A \subseteq M (2, t)} (x - 1)^{k (A) - 1} (y - 1)^{| E (A) | - | V (A) | + k (A)} \end{aligned}$ To get a recursive formula for $T (M (t); x, y)$ , we will exploit the special structure of $M (t + 1)$ . It is known that $\begin{matrix} (9) & T (M (t + 1); x, y) = \sum_{A \subseteq M (t + 1)} (x - 1)^{k (A) - 1} (y - 1)^{| E (A) | - | V (A) | + k (A)} \end{matrix}$ Figure 1 shows that $M (t + 1)$ is created from six copies of $M (t)$ by merging some special nodes and adding an additional edge $e_{t + 1}$ . Let the six copies of $M (t)$ be denoted by $M_{i} (t), i = 1, \dots, 6$ . Consequently, let $A_{i}$ be a subgraph of $M_{i} (t), i = 1, \dots, 6$ , respectively. Define $E$ to be $\begin{matrix} (10) & E = {\begin{matrix} {e_{t + 1}} \\ ϕ \end{matrix} \end{matrix}$ As a result, any spanning subgraph $A$ of $M (t + 1)$ can be identified by the spanning subgraphs $A_{i}$ of the six copies $M_{i} (t), i = 1, \dots, 6$ with $E$ . Thus, it is convenient to express the Tutte polynomial of $M (t + 1)$ as $\begin{matrix} (11) & T (M (t + 1); x, y) = \sum_{A = (⋃_{i = 1}^{6} A_{i}) \cup E} (x - 1)^{k (A) - 1} (y - 1)^{| E (A) | - | V (A) | + k (A)} \end{matrix}$

Now, we are ready to state the following theorem.

Theorem 1. Tutte polynomial of the model network $M (t + 1)$ is $\begin{matrix} (12) & T (M (t + 1); x, y) = T_{1, t + 1} (x, y) + (x - 1) P_{2, t + 1} (x, y), \end{matrix}$ where $\begin{aligned} T_{1, t + 1} (x, y) = y (y - 1) T_{1, t}^{6} (x, y) + 6 y T_{1, t}^{5} (x, y) P_{2, t} (x, y) + (6 x y - 6 y + 9) T_{1, t}^{4} (x, y) P_{2, t}^{2} (x, y) \\ + (2 x^{2} y - 4 x y + 18 x + 2 y - 18) T_{1, t}^{3} (x, y) P_{2, t}^{3} (x, y) + 15 (x - 1)^{2} T_{1, t}^{2} (x, y) P_{2, t}^{4} (x, y) \\ (13) & + 6 (x - 1)^{3} T_{1, t} (x, y) P_{2, t}^{5} (x, y) + (x - 1)^{4} P_{2, t}^{6} (x, y), \end{aligned}$ $\begin{aligned} P_{2, t + 1} (x, y) = \frac{T_{2, t + 1} (x, y)}{x - 1} = 9 T_{1, t}^{4} (x, y) P_{2, t}^{2} (x, y) + 18 (x - 1) T_{1, t}^{3} (x, y) P_{2, t}^{3} (x, y) \\ (14) & + 15 (x - 1)^{2} T_{1, t}^{2} (x, y) P_{2, t}^{4} (x, y) + 6 (x - 1)^{3} T_{1, t} (x, y) P_{2, t}^{5} (x, y) + (x - 1)^{4} P_{2, t}^{6} (x, y), \end{aligned}$ with initial conditions $T_{1, 0} (x, y) = 1$ and $P_{2, 0} (x, y) = 1$ .

Proof. The initial conditions are obvious since $M (0)$ is a path of length one. To prove relations ( $12$ ), ( $13$ ), and ( $14$ ), we need to investigate all possible spanning subgraphs $A$ of $M (t + 1)$ and analyze their corresponding contributions to $T (M (t + 1); x, y)$ .

Let’s start with spanning subgraphs where the special nodes $a_{t + 1}$ and $b_{t + 1}$ belong to the same component. There are 13 distinguish configurations of spanning subgraphs $A$ satisfying this property. Figures 3, 4 and 5 show the possible configurations associated with their contributions. We find that $\begin{matrix} T_{1, t + 1} (x, y) = y (y - 1) T_{1, t}^{6} + \frac{6 y}{x - 1} T_{1, t}^{5} T_{2, t} + \frac{6 x y + 9}{(x - 1)^{2}} T_{1, t}^{4} T_{2, t}^{2} \\ + \frac{2 x y + 16}{(x - 1)^{2}} T_{1, t}^{3} T_{2, t}^{3} + \frac{15}{(x - 1)^{2}} T_{1, t}^{2} T_{2, t}^{4} + \frac{6}{(x - 1)^{2}} T_{1, t} T_{2, t}^{5} + \frac{1}{(x - 1)^{2}} T_{2, t}^{6} \end{matrix}$
Let’s discuss the spanning subgraphs where the special nodes $a_{t + 1}$ and $b_{t + 1}$ belong to two different components. There are 5 different configurations of spanning trees $A$ with the above mentioned property. Figure 6 depicts this case. We also get $\begin{matrix} T_{2, t + 1} (x, y) = \frac{9}{x - 1} T_{1, t}^{4} T_{2, t}^{2} + \frac{18}{x - 1} T_{1, t}^{3} T_{2, t}^{3} + \frac{15}{x - 1} T_{1, t}^{2} T_{2, t}^{4} + \frac{6}{x - 1} T_{1, t} T_{2, t}^{5} + \frac{1}{x - 1} T_{2, t}^{6} . \end{matrix}$

Figure 4. (a), (b), (c), (d) and (e) have contributions $\frac{9}{(x - 1)^{2}} T_{1, t}^{4} T_{2, t}^{2}, \frac{18}{(x - 1)^{2}} T_{1, t}^{3} T_{2, t}^{3}, \frac{15}{(x - 1)^{2}} T_{1, t}^{2} T_{2, t}^{4}, \frac{6}{(x - 1)^{2}} T_{1, t} T_{2, t}^{5}$ , and $\frac{1}{(x - 1)^{2}} T_{2, t}^{6}$

Figure 5. (a), (b) and (c) have contributions $\frac{6}{x - 1} T_{1, t}^{5} T_{2, t}, \frac{6}{x - 1} T_{1, t}^{4} T_{2, t}^{2}$ , and $\frac{2}{x - 1} T_{1, t}^{3} T_{2, t}^{3}$

It is clear that $x - 1$ divides $T_{2, t} (x, y), t \geq 0$ . Thus, we put $T_{2, t} (x, y) = (x - 1) P_{2, t} (x, y)$ and the proof is completed.

4. Applications

4.1. Evaluations of $T (M (t); x, t)$

Many graph invarients can be simply obtained from the Tutte polynomial of the graph. In what comes, we shall exploit some evaluations of the Tutte polynomial of the proposed model.

4.1.1. Number of acyclic orientations of model $M (t)$

The number of acyclic orientations $a (G)$ of a graph $G$ is a crucial quantity in graph theory with related applications in various areas such as social sciences, optimization, computer science and other fields[22]. Stanley[30] studied the relation between $a (G)$ and the chromatic polynomial $P (G; x)$ . It is also known that $a (G)$ can be calculated by the aid of the Tutte polynomial since $a (G) = T (G; 2, 0)$ . Therefore we shall apply this result to our model $M (t)$ to get an explicit formula for $a (M (t))$ .

Theorem 2. The number of acyclic orientations of $M (t)$ is given by $\begin{matrix} (15) & a (M (t)) = 2 \times 49^{\frac{1}{5} (6^{t} - 1)} . \end{matrix}$

Proof. Since $T (G; 2, 0) = a (G) .$ Thus, we put $x = 2, y = 0$ in ( $12$ ) $a (M (t + 1)) = T (M (t + 1); 2, 0) = T_{1, t + 1} (2, 0) + P_{2, t + 1} (2, 0)$ From ( $13$ ) and ( $14$ ), we find that $T_{1, t + 1} (2, 0) = P_{2, t + 1} (2, 0),$ and $\begin{matrix} (16) & T_{1, t + 1} (2, 0) = 49 T_{1, t}^{6} (2, 0), \end{matrix}$ with initial condition $T_{1, 0} (2, 0) = 1$ . Solving [acyclic], we get $T_{1, t} (2, 0) = 49^{\frac{1}{5} (6^{t} - 1)} .$ This completes the required result.

4.1.2. Number of spanning trees of model $M (t)$

We shall evaluate an explicit formula for the number of spanning trees of network model $M (t)$ as an application of the Tutte polynomial of $M (t)$ .

Theorem 3. The number of spanning trees of $M (t)$ is given by $\begin{matrix} (17) & τ (M (t)) = 3 λ_{t}^{4} (3 + 2 λ_{t}) \prod_{k = 0}^{t - 2} (9 λ_{t - k - 1}^{4})^{6^{k + 1}}, \end{matrix}$ where $λ_{t} = 3 (1 - (\frac{2}{3})^{t})$ .

Proof. It is a renowned result that $T (G; 1, 1) = τ (G) .$ Thus, we put $x = y = 1$ in ( $12$ ) $τ (M (t + 1)) = T (M (t + 1); 1, 1) = T_{1, t + 1} (1, 1)$ From ( $13$ ) and ( $14$ ), we have system of difference equations in the form $\begin{array}{rcl} (18) & τ (M (t + 1)) & = & 6 τ^{5} (M (t)) P_{2, t} (1, 1) + 9 τ^{4} (M (t)) P_{2, t}^{2} (1, 1) \\ (19) & P_{2, t + 1} (1, 1) & = & 9 τ^{4} (M (t)) P_{2, t}^{2} (1, 1), \end{array}$ with initial conditions $τ (M (0)) = P_{2, 0} (1, 1) = 1$ .
Using ( $18$ ) and ( $19$ ), we can deduce that $\begin{aligned} \frac{τ (M (t))}{P_{2, t} (1, 1)} & = & 1 + \frac{2}{3} \frac{τ (M (t - 1))}{P_{2, t - 1} (1, 1)} = 3 (1 - {(\frac{2}{3})}^{t + 1}) \end{aligned}$ We can say that $τ (M (t)) = λ_{t + 1} P_{2, t} (1, 1),$ where $λ_{t} = 3 (1 - {(\frac{2}{3})}^{t})$ . Now, we substitute in ( $19$ ) $\begin{aligned} P_{2, t} (1, 1) & = & 9 λ_{t}^{4} P_{2, t - 1}^{6} (1, 1) = 9 λ_{t}^{4} {(9 λ_{t - 1}^{4} P_{2, t - 2}^{6} (1, 1))}^{6} = (9 λ_{t}^{4}) {(9 λ_{t - 1}^{4})}^{6} \dots {(9 λ_{t - k + 1}^{4})}^{6^{k - 1}} P_{2, t - k}^{6^{k}} (1, 1) \\ = & \prod_{k = 0}^{t - 1} {(9 λ_{t - k}^{4})}^{6^{k}} \end{aligned}$ Back to ( $19$ ), we find that $\begin{aligned} τ (M (t)) & = & 9 λ_{t}^{4} P_{2, t - 1}^{6} (1, 1) + 6 λ_{t}^{5} P_{2, t - 1}^{6} (1, 1) = 3 λ_{t}^{4} (3 + 2 λ_{t}) P_{2, t - 1}^{6} = 3 λ_{t}^{4} (3 + 2 λ_{t}) \prod_{k = 0}^{t - 2} {(9 λ_{t - k - 1}^{4})}^{6^{k + 1}} . \end{aligned}$

4.1.3. Entropy of spanning trees of $M (t)$

The entropy of spanning trees or asymptotic complexity of any graph network is a graph invarient which measures the robustness of the graph. We can say that the higher the entropy of spanning trees, the higher the robustness of the graph.

Theorem 4. The spanning trees entropy of model $M (t)$ is given by $\begin{matrix} (20) & ρ (M (t)) = lim_{| V (M (t)) | \to \infty} \frac{\ln τ (M (t))}{| V (M (t)) |} \approx 0.64 \end{matrix}$

Proof. We have $\begin{aligned} ρ (M (t)) & = & lim_{| V (M (t)) | \to \infty} \frac{\ln τ (M (t))}{| V (M (t)) |} = lim_{t \to \infty} \frac{\ln (3 λ_{t}^{4} (3 + 2 λ_{t}) \prod_{k = 0}^{t - 2} {(9 λ_{t - k - 1}^{4})}^{6^{k + 1}})}{\frac{4}{5} 6^{t} + \frac{6}{5}} \\ \approx & lim_{t \to \infty} \frac{6^{t - 3} \ln 9 λ_{3}^{4} + 6^{t - 2} \ln 9 λ_{2}^{4} + 6^{t - 1} \ln 9 λ_{1}^{4}}{\frac{4}{5} 6^{t}} \approx 0.64 . \end{aligned}$

4.2. Tutte polynomial of model $N (t)$

The network model $N (t)$ has been presented in [1] and it can be obtained from the network model $M (t)$ by replacing each edge in $M (t)$ by a path of length 2 as shown in Figure 7.

Figure 7. The diagrams of network model $N (t)$ at $t = 0, 1, 2$ .

As presented, the network model $N (t)$ , studied in[1], is obtained from the network model $M (t)$ by replacing each edge in $M (t)$ by a path of length two. We can also deduce the Tutte polynomial of $N (t)$ by the aid of the Tutte polynomial of $M (t)$ based on the results published in [29].
We shall rely on the work achieved by Y. Liao et al. [29] to compute the Tutte polynomial of model $N (t)$ .

Theorem 5. The Tutte polynomial of the network model $N (t)$ is given by $\begin{matrix} (21) & T (N (t); x, y) = (1 + x)^{\frac{2}{5} (6^{t} - 1)} T (M (t); x^{2}, \frac{y + x}{1 + x}) . \end{matrix}$

As a result, we will evaluate the number of spanning trees of $N (t)$ and compare it with the main result presented by Ma et al. [1]. In [1], a formula for calculating the number of spanning trees was presented in Theorem 6 which isn’t redress. In the following, we display the correct formula for calculating the number of spanning trees in Theorem 1. A total verification with more points of interest than the one displayed in[1] is given.

Theorem 6. The number of spanning trees of the network model $N (t)$ is given by $\begin{matrix} (22) & τ (N (t)) = 2^{\frac{2}{5} (6^{t} - 1)} τ (M (t)) . \end{matrix}$

Note that this result is inconsistent with the previous work [1]. We will verify the accuracy of our result by using Matlab package (R2019a). The numerical examples were run on a computer with an Intel(R) processor running at 2.50 GHz using 8.00 GB of RAM, running Windows.

Comparison between results by Matlab at $t = 0, \dots, 3$
$t$	$τ (N (t))$ (our results)	$τ (N (t))$ (results in[1])	$τ (N (t))$ (Matlab results)
0	1	1	1
1	60	60	60
2	$1.2765 \times 10^{12}$	$1.3201 \times 10^{11}$	$1.2765 \times 10^{12}$
3	$8.4134 \times 10^{73}$	$6.7730 \times 10^{66}$	$8.4134 \times 10^{73}$

Table 1 shows the number of spanning trees of $N (t)$ for the first forth values of $t$ . Initially, at $t = 0, 1$ , our results, the results from [1], and numerical results from Matlab code are identical. Whereas at $t = 2, 3$ , our results are the same as the results obtained from Matlab code, and differ with the results proposed in [1].

5. Conclusion

Self-similar networks are hugely investigated in many fields of studies. Numerous of the characteristics and properties of self-similar networks can be recognized from the Tutte polynomial. The Tutte polynomial of graphs is a considerable graph invariant that includes other graph invariants as a specialization. We find that the Tutte polynomial of two self-similar networks, namely $M (t)$ and $N (t)$ . In particular, the exact formulae of the number of the spanning trees of both of them are deduced. Furthermore, we find that our formula of the number of spanning trees of $N (t)$ is more correct than the formula presented by Ma et al.[1].

Declarations

Data availability: Not applicable.
Conflicts of interests: The authors declare that they have no conflicting of interests.
Author’s contributions: AWA suggested the considered problem. FE analyzed the problem and was a major contributer in writing the manuscript. All authors read and approved the final manuscript.
Funding: Not applicable.

Conflict of Interest

The authors declare no conflict of interests.

References:

Ma, F., Su, J. and Yao, B., 2018. A recursive method for calculating the total number of spanning trees and its applications in self-similar small-world scale-free network models. The European Physical Journal B, 91, pp.1-14.[Google Scholor]
Tutte, W.T., 1954. A contribution to the theory of chromatic polynomials. Canadian journal of mathematics, 6, pp.80-91.[Google Scholor]
Tutte, W.T., 1967. On dichromatic polynomials. Journal of Combinatorial Theory, 2(3), pp.301-320.[Google Scholor]
Birkhoff, G.D., 1912. A determinant formula for the number of ways of coloring a map. The Annals of Mathematics, 14(1/4), pp.42-46.[Google Scholor]
Whitney, H., 1932. A logical expansion in mathematics. Bulletin of the American Mathematical Society, 38(8), pp.572-579.[Google Scholor]
Oxley, J.G. and Welsh, D.J., 1979. The Tutte polynomial and percolation. Graph theory and related topics, pp.329-339.[Google Scholor]
Brylawski, T.H., 1972. A decomposition for combinatorial geometries. Transactions of the American Mathematical Society, 171, pp.235-282.[Google Scholor]
Welsh, D., 1999. The tutte polynomial. Random Structures & Algorithms, 15(3-4), pp.210-228.[Google Scholor]
Bernardi, O., K{\’a}lm{\’a}n, T. and Postnikov, A., 2022. Universal tutte polynomial. Advances in Mathematics, 402, p.108355.[Google Scholor]
Bencs, F. and Csikv{\’a}ri, P., 2022. Evaluations of Tutte polynomials of regular graphs. Journal of Combinatorial Theory, Series B, 157, pp.500-523.[Google Scholor]
Bollob{\’a}s, B., 1998. Modern graph theory (Vol. 184). Springer Science & Business Media.[Google Scholor]
Kang, S.M., Nizami, A.R., Munir, M., Nazeer, W. and Kwun, Y.C., 2016. Tutte polynomials with applications. Global Journal of Pure and Applied Mathematics, 12(6), pp.4781-4797.[Google Scholor]
Ellis-Monaghan, J.A. and Merino, C., 2011. Graph polynomials and their applications I: The Tutte polynomial. Structural analysis of complex networks, pp.219-255.[Google Scholor]
Aguero, J.R., Takayesu, E., Novosel, D. and Masiello, R., 2017. Modernizing the grid: Challenges and opportunities for a sustainable future. IEEE Power and Energy Magazine, 15(3), pp.74-83.[Google Scholor]
Amir, S., Nor Sabirin, M. and Subban, R.H.Y., 2010. The investigation on ionic conduction of PEMA based solid polymer electrolytes. Advanced Materials Research, 93, pp.381-384.[Google Scholor]
Bassett, D.S. and Bullmore, E.T., 2017. Small-world brain networks revisited. The Neuroscientist, 23(5), pp.499-516.[Google Scholor]
Cai, Q., Ang, H., Alam, S., Ma, C. and Duong, V., 2020, July. Enhancing the robustness of airport networks by removing links. In 2020 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-7). IEEE. [Google Scholor]
Hinz, A.M. and Movarraei, N., 2020. The Hanoi Graph $H_{3}^{4}$ . Discussiones Mathematicae Graph Theory, 40(4), pp.1095-1109.[Google Scholor]
Hinz, A.M., 2017. Open problems for Hanoi and Sierpinski graphs. Electronic Notes in Discrete Mathematics, 63, pp.23-31.[Google Scholor]
Teufl, E. and Wagner, S., 2007. Enumeration problems for classes of self-similar graphs. Journal of Combinatorial Theory, Series A, 114(7), pp.1254-1277.[Google Scholor]
Chen, H. and Deng, H., 2016. Tutte polynomial of scale-free networks. Journal of Statistical Physics, 163, pp.714-732.[Google Scholor]
Conte, A., Grossi, R., Marino, A. and Rizzi, R., 2016. Listing acyclic orientations of graphs with single and multiple sources. In LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings 12 (pp. 319-333). Springer Berlin Heidelberg. [Google Scholor]
Crapo, H.H., 1969. The tutte polynomial. Aequationes Mathematicae, 3, pp.211-229.[Google Scholor]
Gong, H. and Jin, X.A., 2017. A general method for computing Tutte polynomials of self-similar graphs. Physica A: Statistical Mechanics and its Applications, 483, pp.117-129.[Google Scholor]
Liao, Y., Aziz-Alaoui, M.A., Zhao, J. and Hou, Y., 2019. The behavior of Tutte polynomials of graphs under five graph operations and its applications. Applied Mathematics and Computation, 363, p.124641.[Google Scholor]
Liao, Y., Hou, Y. and Shen, X., 2013. Tutte polynomial of a small-world Farey graph. Europhysics Letters, 104(3), p.38001.[Google Scholor]
Liao, Y., Hou, Y. and Shen, X., 2014. Tutte polynomial of the Apollonian network. Journal of Statistical Mechanics: Theory and Experiment, 2014(10), p.P10043.[Google Scholor]
Peng, J., Xiong, J. and Xu, G., 2015. Tutte polynomial of pseudofractal scale-free web. Journal of Statistical Physics, 159, pp.1196-1215.[Google Scholor]
Y. Liao, Y., Xie, X., Hou, Y. and Aziz-Alaoui, M.A., 2019. Tutte polynomials of two self-similar network models. Journal of Statistical Physics, 174, pp.893-905.[Google Scholor]
Stanley, R.P., 1973. Acyclic orientations of graphs. Discrete Mathematics, 5(2), pp.171-178.[Google Scholor]

[1] Ma, F., Su, J. and Yao, B., 2018. A recursive method for calculating the total number of spanning trees and its applications in self-similar small-world scale-free network models. The European Physical Journal B, 91, pp.1-14.[Google Scholor]

[2] Tutte, W.T., 1954. A contribution to the theory of chromatic polynomials. Canadian journal of mathematics, 6, pp.80-91.[Google Scholor]

[3] Tutte, W.T., 1967. On dichromatic polynomials. Journal of Combinatorial Theory, 2(3), pp.301-320.[Google Scholor]

[4] Birkhoff, G.D., 1912. A determinant formula for the number of ways of coloring a map. The Annals of Mathematics, 14(1/4), pp.42-46.[Google Scholor]

[5] Whitney, H., 1932. A logical expansion in mathematics. Bulletin of the American Mathematical Society, 38(8), pp.572-579.[Google Scholor]

[6] Oxley, J.G. and Welsh, D.J., 1979. The Tutte polynomial and percolation. Graph theory and related topics, pp.329-339.[Google Scholor]

[7] Brylawski, T.H., 1972. A decomposition for combinatorial geometries. Transactions of the American Mathematical Society, 171, pp.235-282.[Google Scholor]

[8] Welsh, D., 1999. The tutte polynomial. Random Structures & Algorithms, 15(3-4), pp.210-228.[Google Scholor]

[9] Bernardi, O., K{\’a}lm{\’a}n, T. and Postnikov, A., 2022. Universal tutte polynomial. Advances in Mathematics, 402, p.108355.[Google Scholor]

[10] Bencs, F. and Csikv{\’a}ri, P., 2022. Evaluations of Tutte polynomials of regular graphs. Journal of Combinatorial Theory, Series B, 157, pp.500-523.[Google Scholor]

[11] Bollob{\’a}s, B., 1998. Modern graph theory (Vol. 184). Springer Science & Business Media.[Google Scholor]

[12] Kang, S.M., Nizami, A.R., Munir, M., Nazeer, W. and Kwun, Y.C., 2016. Tutte polynomials with applications. Global Journal of Pure and Applied Mathematics, 12(6), pp.4781-4797.[Google Scholor]

[13] Ellis-Monaghan, J.A. and Merino, C., 2011. Graph polynomials and their applications I: The Tutte polynomial. Structural analysis of complex networks, pp.219-255.[Google Scholor]

[14] Aguero, J.R., Takayesu, E., Novosel, D. and Masiello, R., 2017. Modernizing the grid: Challenges and opportunities for a sustainable future. IEEE Power and Energy Magazine, 15(3), pp.74-83.[Google Scholor]

[15] Amir, S., Nor Sabirin, M. and Subban, R.H.Y., 2010. The investigation on ionic conduction of PEMA based solid polymer electrolytes. Advanced Materials Research, 93, pp.381-384.[Google Scholor]

[16] Bassett, D.S. and Bullmore, E.T., 2017. Small-world brain networks revisited. The Neuroscientist, 23(5), pp.499-516.[Google Scholor]

[17] Cai, Q., Ang, H., Alam, S., Ma, C. and Duong, V., 2020, July. Enhancing the robustness of airport networks by removing links. In 2020 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-7). IEEE. [Google Scholor]

[18] Hinz, A.M. and Movarraei, N., 2020. The Hanoi Graph $H_{3}^{4}$ . Discussiones Mathematicae Graph Theory, 40(4), pp.1095-1109.[Google Scholor]

[19] Hinz, A.M., 2017. Open problems for Hanoi and Sierpinski graphs. Electronic Notes in Discrete Mathematics, 63, pp.23-31.[Google Scholor]

[20] Teufl, E. and Wagner, S., 2007. Enumeration problems for classes of self-similar graphs. Journal of Combinatorial Theory, Series A, 114(7), pp.1254-1277.[Google Scholor]

[21] Chen, H. and Deng, H., 2016. Tutte polynomial of scale-free networks. Journal of Statistical Physics, 163, pp.714-732.[Google Scholor]

[22] Conte, A., Grossi, R., Marino, A. and Rizzi, R., 2016. Listing acyclic orientations of graphs with single and multiple sources. In LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings 12 (pp. 319-333). Springer Berlin Heidelberg. [Google Scholor]

[23] Crapo, H.H., 1969. The tutte polynomial. Aequationes Mathematicae, 3, pp.211-229.[Google Scholor]

[24] Gong, H. and Jin, X.A., 2017. A general method for computing Tutte polynomials of self-similar graphs. Physica A: Statistical Mechanics and its Applications, 483, pp.117-129.[Google Scholor]

[25] Liao, Y., Aziz-Alaoui, M.A., Zhao, J. and Hou, Y., 2019. The behavior of Tutte polynomials of graphs under five graph operations and its applications. Applied Mathematics and Computation, 363, p.124641.[Google Scholor]

[26] Liao, Y., Hou, Y. and Shen, X., 2013. Tutte polynomial of a small-world Farey graph. Europhysics Letters, 104(3), p.38001.[Google Scholor]

[27] Liao, Y., Hou, Y. and Shen, X., 2014. Tutte polynomial of the Apollonian network. Journal of Statistical Mechanics: Theory and Experiment, 2014(10), p.P10043.[Google Scholor]

[28] Peng, J., Xiong, J. and Xu, G., 2015. Tutte polynomial of pseudofractal scale-free web. Journal of Statistical Physics, 159, pp.1196-1215.[Google Scholor]

[29] Y. Liao, Y., Xie, X., Hou, Y. and Aziz-Alaoui, M.A., 2019. Tutte polynomials of two self-similar network models. Journal of Statistical Physics, 174, pp.893-905.[Google Scholor]

[30] Stanley, R.P., 1973. Acyclic orientations of graphs. Discrete Mathematics, 5(2), pp.171-178.[Google Scholor]

Contents

Ars Combinatoria