# Complexity of Some Generalized Operations on Networks

Authors: Muhammad Javaid; Hafiz Usman Afzal; Shaohui Wang
Journal: Complexity
 (2021)

---

## Abstract

The number of spanning trees in a network determines the totality of acyclic and connected components present within. This number is termed as complexity of the network. In this article, we address the closed formulae of the complexity of networks’ operations such as duplication (split, shadow, and vortex networks ofSn), sum (Sn+W3, Sn+K2, and Cn∘K2+K1), product (Sn⊠K2 and Wn∘K2), semitotal networks (QSn and RSn), and edge subdivision of the wheel. All our findings in this article have been obtained by applying the methods from linear algebra, matrix theory, and Chebyshev polynomials. Our results shall also be summarized with the help of individual plots and relative comparison at the end of this article.


---

## Body

## 1. Introduction

Preliminarily, the finite, connected, and simple networkΓ=VΓ,EΓ shall be our consideration. The complexity (number of spanning trees in a network) is an enormously useful network invariant and is significantly studied in algebraic graph theory, combinatorics, and networking. It admits main connections to computer networking and certain branches of engineering that are related to urban planning (civil engineering) specifically. In fact, the more rigidity and accuracy of a network is ensured by a greater number of spanning trees. Thus, the complexity refers to more perfectness and quality in a network. For further details of its applications, see [1–6].No general complexity function for an infinite family of networks has been obtained in the literature yet. However, there is a scope of determining closed formulae to find out the complexity of networks of ordern, especially when the value of n is sufficiently large. With the increase in the order of a network Γ, it is significant to recapitulate the trend of its complexity function τΓ. Among the foremost of such findings, the credit of determining the complexity function of Kn, as τKn=nn−2 goes to Cayley [7]. In the same article, another very prominent result proposed by him is the complexity of the complete bipartite network which he enumerated as τKm,n=mn−1nm−1. The expression for the complexity of Mobius ladder is derived to be τMm=m/22+3m+2−mm+2, for m≥2 [8].Recently, determining the number of spanning trees of networks using the determinants of certain matrices has become a hot topic. The most famous among these is Kirchhoff’s matrix tree theorem [4]. The aforesaid famous theorem states that the complexity of a network is a cofactor of its Kirchhoff’s matrix, where the Kirchhoff’s matrix of a network Γ is given as KΓ=DΓ−AΓ.The contraction-deletion theorem is a combinatorial technique to enumerate the number of spanning trees of a network. Lete∈EΓ, then the complexity of Γ can be calculated iteratively by using(1)tΓ=tΓ|e+tΓ−e,where Γ|e is obtained by contracting e=uv in Γ until the two vertices u and v coincide and Γ−e is just the edge deletion with respect to the edge e [9].The Laplacian spectrum is also helpful for the calculation of the complexity of the networkΓ. Let μ1,μ2,…,μm be the eigenvalues of the Laplacian matrix H of Γ. In [10], it is shown that(2)τΓ=1m∏i=1m−1μi.This method is a complicated one, and complexity of larger networks becomes cumbersome to calculate in this method. Temperley has proven thatτΓ=1/m2H+1, where 1 is the m×m matrix with all 1 entries. Some recent work on the enumeration of the complexity of various families of networks can be found in [2, 9, 11–15].


### 1.1. Definitions and Preliminaries

Temperley’s equation mentioned above straightforwardly gives us the following lemma.Lemma 1.
(see [16]). Let Γ be an m-order network, then(3)τΓ=1m2detmI−DΓ¯+AΓ¯,where Γ¯ represents the complement of the network Γ.The above formula attains significance while enumerating the complexity as it representsτΓ as the determinant of a specific matrix rather than eigenvalues or cofactor.The first-kind Chebyshev polynomials are defined as the solution of the iterative relation.(4)Tm+1x−2xTmx+Tm−1x=0,T0x=1,T1x=x.The standard solution of the above iterative relation gives(5)Tmx=12x+x2−1m+x−x2−1m,m≥1.The second-kind Chebyshev Polynomials are defined as the solution of the following iterative relation:(6)Um+1x−2xUmx+Um−1x=0,U0x=1,U1x=x.The standard solution of the above iterative relation gives(7)Umx=12x2−1x+x2−1m+1−x−x2−1m+1,m≥1.Identity (7) is valid for all complex values of x except x=±1.Both first- and second-kind Chebyshev polynomials have a strong link with the determinants [17].Lemma 2.
(see [18, 19]).(i)
∀φ≥3, detAmφ=2Tmφ/2−1, where(8)Amφ=φ−100…000−1−1φ−10…00000−1φ−1…000000−1φ…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…φ−1000000…−1φ−100000…0−1φ−1−1000…00−1φ.(ii)
∀φ≥4, m≥3, detBmφ=2φ+m−3/φ−3Tmφ−1/2−1, where(9)Bmφ=φ011…11100φ01…111110φ0…1111110φ…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…φ0111111…0φ011111…10φ00111…110φ.(iii)
∀m,φ; detCmφ=φ−1Um−1φ+1/2, where(10)Cmφ=φ−100…0000−1φ+1−10…00000−1φ+1−1…000000−1φ+1…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…φ+1−1000000…−1φ+1−100000…0−1φ+1−10000…00−1φ.(iv)
∀φ≥2, m≥3, detDmφ=m+φ−2Um−1φ/2, where(11)Dmφ=φ011…11110φ+101…111110φ+10…1111110φ+1…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…φ+10111111…0φ+1011111…10φ+101111…110φ.Lemma 3.
(see [20]). ∀φ and m, detWmφ=φ+m−1φ−1m−1, where Wmφ is an m×m circulant matrix given as(12)Wmφ=φ111…11111φ11…111111φ1…1111111φ…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…φ1111111…1φ111111…11φ11111…111φ.Lemma 4.
(see [21]). Let P, Q, R, and S be the block matrices of orders α×α, α×β, β×α, and β×β, respectively. Then,(13)detPQRS=detP×detS−RP−1Q=detS×detP−QS−1R,where P and Q are nonsingular matrices.Throughout the article,Am×n will represent the matrix of order m×n. Ri and Ci will represent the ith row and ith column in a matrix, respectively. Also, the set of determinant operations (∗) performed in Theorem 1 shall be used frequently in all our results.


## 1.1. Definitions and Preliminaries

Temperley’s equation mentioned above straightforwardly gives us the following lemma.Lemma 1.
(see [16]). Let Γ be an m-order network, then(3)τΓ=1m2detmI−DΓ¯+AΓ¯,where Γ¯ represents the complement of the network Γ.The above formula attains significance while enumerating the complexity as it representsτΓ as the determinant of a specific matrix rather than eigenvalues or cofactor.The first-kind Chebyshev polynomials are defined as the solution of the iterative relation.(4)Tm+1x−2xTmx+Tm−1x=0,T0x=1,T1x=x.The standard solution of the above iterative relation gives(5)Tmx=12x+x2−1m+x−x2−1m,m≥1.The second-kind Chebyshev Polynomials are defined as the solution of the following iterative relation:(6)Um+1x−2xUmx+Um−1x=0,U0x=1,U1x=x.The standard solution of the above iterative relation gives(7)Umx=12x2−1x+x2−1m+1−x−x2−1m+1,m≥1.Identity (7) is valid for all complex values of x except x=±1.Both first- and second-kind Chebyshev polynomials have a strong link with the determinants [17].Lemma 2.
(see [18, 19]).(i)
∀φ≥3, detAmφ=2Tmφ/2−1, where(8)Amφ=φ−100…000−1−1φ−10…00000−1φ−1…000000−1φ…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…φ−1000000…−1φ−100000…0−1φ−1−1000…00−1φ.(ii)
∀φ≥4, m≥3, detBmφ=2φ+m−3/φ−3Tmφ−1/2−1, where(9)Bmφ=φ011…11100φ01…111110φ0…1111110φ…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…φ0111111…0φ011111…10φ00111…110φ.(iii)
∀m,φ; detCmφ=φ−1Um−1φ+1/2, where(10)Cmφ=φ−100…0000−1φ+1−10…00000−1φ+1−1…000000−1φ+1…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…φ+1−1000000…−1φ+1−100000…0−1φ+1−10000…00−1φ.(iv)
∀φ≥2, m≥3, detDmφ=m+φ−2Um−1φ/2, where(11)Dmφ=φ011…11110φ+101…111110φ+10…1111110φ+1…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…φ+10111111…0φ+1011111…10φ+101111…110φ.Lemma 3.
(see [20]). ∀φ and m, detWmφ=φ+m−1φ−1m−1, where Wmφ is an m×m circulant matrix given as(12)Wmφ=φ111…11111φ11…111111φ1…1111111φ…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…φ1111111…1φ111111…11φ11111…111φ.Lemma 4.
(see [21]). Let P, Q, R, and S be the block matrices of orders α×α, α×β, β×α, and β×β, respectively. Then,(13)detPQRS=detP×detS−RP−1Q=detS×detP−QS−1R,where P and Q are nonsingular matrices.Throughout the article,Am×n will represent the matrix of order m×n. Ri and Ci will represent the ith row and ith column in a matrix, respectively. Also, the set of determinant operations (∗) performed in Theorem 1 shall be used frequently in all our results.


## 2. Main Results

The realm of generating new structures by applying general operations to the existing ones always remains open in networking. In this section, we shall present our main findings consisting of the enumerated closed formulae of the generalized operation on certain networks. The necessary definition of a network’s operation [22, 23] shall be provided before the respective result.Theorem 1.
For alln, the complexity of the network Sn+W3 is given by(14)τSn+W3=5n−1n+54.Proof.
Consider the networkSn+W3 with VSn+W3=n+5 and ESn+W3=5n+10, see Figure 1.
Applying Lemma1, we have(15)τSn+W3=1n+52detn+5I−D¯+A¯=1n+52detn+500000000…00000n+50000000…000000n+5000000…0000000n+500000…00000000n+50000…0000000006111…1111000001611…1111000001161…1111000001116…1111⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮000001111…6111000001116…1611000001116…1161000001116…1116n+5×n+5.
Now, we perform the following operations simultaneously on the above determinant:(i)
Adding all columns toC1(ii)
Takingn + 5 common from C1. −−−−−−−−▶∗(iii)
SubtractingC1 from all columns(iv)
Expanding alongR1
These operations yield(16)=detn+4−1−1−1−1−1−1−1…−1−1−1−1−1n+4−1−1−1−1−1−1…−1−1−1−1−1−1n+4−1−1−1−1−1…−1−1−1−1−1−1−1n+4−1−1−1−1…−1−1−1−1−1−1−1−15000…0000−1−1−1−10500…0000−1−1−1−10050…0000−1−1−1−10005…0000⋮⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮−1−1−1−10000…5000−1−1−1−10000…0500−1−1−1−10000…0050−1−1−1−15000…0005n+4×n+4⇒τSn+W3=detP4×4Q4×nRn×4Sn×nn+4×n+4.
By using Lemma4, we obtain(17)τSn+W3=detS⋅detP−QS−1R=5ndet4n+205−n+55−n+55−n+55−n+554n+205−n+55−n+55−n+55−n+554n+205−n+55−n+55−n+55−n+554n+205=5nn+5544n+20−n+511114n+20−n+511114n+20−n+511114n+20−n+5.
Using Lemma3, we have(18)τSn+W3=5n−4n+544n+20−n+5+34n+20−n+5−13⇒τSn+W3=5n−1n+54.Figure 1
The networkSn+W3.Definition 1.
The shadowD2Γ1 of a network Γ1 is obtained by taking another copy of Γ1, say Γ2, and then by making all those vertices ui∈VΓ1 adjacent to the corresponding adjacent vertices vi∈VΓ2.Theorem 2.
For alln, the complexity of the network D2Sn is given by(19)τD2Sn=n⋅22n.Proof.
Consider the networkD2Sn with VD2Sn=2n+2 and ED2Sn=4n, see Figure 2.
Applying Lemma1, we have(20)τD2Sn=12n+22det2n+2I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of the network D2Sn, respectively.(21)=12n+22det2n+11000…000000…00012n+1000…000000…00000311…111111…11100131…111111…11100113…111111…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00111…311111…11100111…131111…11100111…113111…11100111…111311…11100111…111131…11100111…111113…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00111…111111…31100111…111111…13100111…111111…1132n+2×2n+2=det2n−1−1−1…−1−1−1−1−1−1…−1−1−1−1200…000000…000−1020…000000…000−1002…000000…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1000…200000…000−1000…020000…000−1000…002000…000−1000…000200…000−1000…000020…000−1000…000002…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1000…000000…200−1000…000000…020−1000…000000…0022n+1×2n+1⇒τD2Sn=detP1×1Q1×2nR2n×1S2n×2n2n+1×2n+1.
By using Lemma4, we obtain(22)τD2Sn=detS.detP−QS−1R=22ndet2n−n,τD2Sn=n.22n.Figure 2
The shadow networkD2Sn.Definition 2.
The splitting networkS′Γ1 of a network Γ1 is obtained by taking a vertex set, say V2, corresponding to VΓ1 and then by making all those vertices ui∈VΓ1 adjacent to the corresponding vertices vi∈V2 that preserve the adjacency of Γ1.Theorem 3.
For alln, the complexity of the splitting network S′Sn is given by(23)τS′Sn=n.2n−1.Proof.
Let us consider the networkS′Sn with VS′Sn=2n+2 and ES′Sn=3n, see the general formation in Figure 3.
Applying Lemma1, we have(24)τS′Sn=12n+22det2n+2I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of the splitting network S′Sn, respectively.(25)=12n+22det2n+11000…000000…0001n+1000…000111…11100311…111111…11100131…111111…11100113…111111…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00111…311111…11100111…131111…11100111…113111…11101111…111211…11101111…111121…11101111…111112…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮01111…111111…21101111…111111…12101111…111111…1122n+2×2n+2=detn−1−1−1…−1−1−1000…000−1200…000000…000−1020…000000…000−1002…000000…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1000…200000…000−1000…020000…000−1000…002000…0000000…000100…0000000…000010…0000000…000001…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0000…000000…1000000…000000…0100000…000000…0012n+1×2n+1⇒τS′Sn=detP1×1Q1×2nR2n×1S2n×2n2n+1×2n+1.
By using Lemma4, we obtain(26)τS′Sn=detS.detP−QS−1R=2ndetn−n2⇒τS′Sn=n⋅2n−1.Figure 3
The splitting networkS′Sn.Definition 3.
The strong product of two networksΓ1=VΓ1,EΓ1 and Γ2=VΓ2,EΓ2 is a new network Γ1⊠Γ2 with vertex and edge sets as follows:(27)VΓ1⊠Γ2=VΓ1×VΓ2.
EΓ1⊠Γ2=u1,u2v1,v2,wheneveru1=v1&u2∼v2oru1∼v1&u2=v2oru1∼v1&u2∼v2,whereu1,u2,v1,v2∈VG1⊠G2.Theorem 4.
For alln, the complexity of the strong product Sn⊠P2 is given by(28)τSn⊠K2=8nn+1.Proof.
Consider the networkSn⊠K2 with VSn⊠K2=2n+2 and ESn⊠K2=5n+1, see its general formation in Figure 4.
Applying Lemma1, we have(29)τSn⊠K2=12n+22det2n+2I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of the network Sn⊠K2, respectively.(30)=12n+22det2n+20000…000000…00002n+2000…000000…00000411…111011…11100141…111101…11100114…111110…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00111…411111…01100111…141111…10100111…114111…11000011…111411…11100101…111141…11100110…111114…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00111…011111…41100111…101111…14100111…110111…1142n+2×2n+2=det2n+1−1−1−1…−1−1−1−1−1−1…−1−1−1−1300…000−100…000−1030…0000−10…000−1003…00000−1…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1000…300000…−100−1000…030000…0−10−1000…003000…00−1−1−100…000300…000−10−10…000030…000−100−1…000003…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1000…−100000…300−1000…0−10000…030−1000…00−1000…0032n+1×2n+1⇒τSn⊠K2=detPn+1×n+1Qn+1×nRn×n+1Sn×n2n+1×2n+1.
By using Lemma4, we obtain(31)τSn⊠K2=detS.detP−QS−1R=3n.−43n+1det5n+3−4111…11111−200…000010−20…0000100−2…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮1000…−20001000…0−2001000…00−201000…000−2n+1×n+1=3n.−43n+1detAn+1×n+1.
Calculating the values ofdetA for n=1,2,3,…,10. We obtain detA=3,−9,24,−60,144,−336,768,−1728,3840,−8448. Upon generalizing for n, we obtain detA=3−2nn+1/−4.(32)⇒τSn⊠K2=3n.−43n+13−2nn+1−4.
Finally, we obtain(33)τSn⊠K2=8nn+1.Figure 4
The strong productSn⊠K2.We define here a new operation namely vortexV′Γ of a network Γ.Definition 4.
The vortexV′G1 of a network Γ1 is obtained by taking a vertex set, say V2, corresponding to VΓ1 and then by making all those vertices ui∈VΓ1 adjacent to those vertices vi∈V2 that do not preserve the adjacency of Γ1.Theorem 5.
For alln, the complexity of the vortex V′Sn is given by(34)τV′Sn=nnn+1n−1.Proof.
Consider the networkV′Sn with VV′Sn=2n+2 and EV′Sn=n2+n+1, see Figure 5.
Applying Lemma1, we have(35)τV′Sn=12n+22det2n+2I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of the vortex V′Sn, respectively.(36)=12n+22detn+20000…000111…11102111…111111…11101n+211…111000…000011n+21…111000…0000111n+2…111000…000⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮01111…n+211000…00001111…1n+21000…00001111…11n+2000…00011000…000n+111…11111000…0001n+11…11111000…00011n+1…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮11000…000111…n+11111000…000111…1n+1111000…000111…11n+1=det1000…000000…0000n+100…000−1−1−1…−1−1−100n+10…000−1−1−1…−1−1−1000n+1…000−1−1−1…−1−1−1⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0000…n+100−1−1−1…−1−1−10000…0n+10−1−1−1…−1−1−10000…00n+1−1−1−1…−1−1−10−1−1−1…−1−1−1n00…0000−1−1−1…−1−1−10n0…0000−1−1−1…−1−1−100n…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0−1−1−1…−1−1−1000…n000−1−1−1…−1−1−1000…0n00−1−1−1…−1−1−1000…00n2n+1×2n+1⇒τV′Sn=detPn+1×n+1Qn+1×nRn×n+1Sn×n2n+1×2n+1.
By using Lemma4, we obtain(37)τV′Sn=detS.detP−QS−1R=nndet1000…00000n−1−1…−1−1−1−10−1n−1…−1−1−1−10−1−1n…−1−1−1−1⋮⋮⋮⋮⋱⋮⋮⋮⋮0−1−1−1…n−1−1−10−1−1−1…−1n−1−10−1−1−1…−1−1n−10−1−1−1…−1−1−1nn+1×n+1=nn−1ndet−n11…11111−n1…111111−n…1111⋮⋮⋮⋱⋮⋮⋮⋮111…−n111111…1−n11111…11−n1111…111−nn×n.
Applying Lemma3,(38)=nn−1n−n+n−1−n−1n−1⇒τV′Sn=nnn+1n−1.Figure 5
The vortex networkV′Sn.Theorem 6.
For alln, the complexity of the network Sn+K2 is given by(39)τSn+K2=3n−22n+62−n+32.Proof.
Consider the networkSn+K2 with VSn+K2=n+3 and ESn+K2=3n+1, see Figure 6.
Applying Lemma1, we have(40)τSn+K2=1n+32detn+3I−D¯+A¯=1n+32detn+3000000…00000n+300000…000000n+30000…00000004111…11110001411…11110001141…11110001114…1111⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮0001111…41110001116…14110001116…11410001116…1114n+3×n+3=detn+2−1−1−1−1−1…−1−1−1−1−1n+2−1−1−1−1…−1−1−1−1−1−13000…0000−1−10300…0000−1−10030…0000−1−10003…0000⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1−10000…3000−1−10000…0300−1−10000…0030−1−15000…0003n+2×n+2⇒τSn+K2=detP2×2Q2×nRn×2Sn×nn+2×n+2.
By using Lemma4, we obtain(41)τSn+K2=detS.detP−QS−1R=3ndet2n+63−n+33−n+332n+63⇒τSn+K2=3n−22n+62−n+32.Figure 6
The networkSn+K2.Theorem 7.
Forn≥3, the complexity of an edge-subdivision of the wheel Wn′ is given by(42)τWn′=22n−2n+1+1.Proof.
Consider the edge-subdivision of wheelWn′ with VWn′=2n+1, EWn′=3n, see Figure 7.
Applying Lemma1, we have(43)τWn′=12n+12det2n+1I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of the network Wn′, respectively.(44)=12n+12detn+1111…111000…0001411…111011…1111141…111101…1111114…111110…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮1111…411111…0111111…141111…1011111…114111…1100011…111311…1110101…111131…1110110…111113…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0111…011111…3110111…101111…1310111…110111…1132n+1×2n+1=det3−10…00−1−100…000−13−1…0000−10…0000−13…00000−1…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…3−10000…−100000…−13−1000…0−10−100…0−13000…00−1−100…000200…0000−10…000020…00000−1…000002…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…−100000…200000…0−10000…020000…00−1000…0022n×2n⇒τWn′=detPn×nQn×nRn×nSn×n2n×2n.
By using Lemma4, we obtain(45)τWn′=detS⋅detP−QS−1R=2ndet52−100…000−1−152−10…00000−152−1…000000−152…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…52−1000000…−152−100000…0−152−1−1000…00−152n×n.
Using Lemma2,(46)=2n.2Tn54−1=2n2n+12n−2⇒τWn′=22n−2n+1+1.Figure 7
An edge-subdivision of the networkWn.Theorem 8.
Forn≥3, the complexity of the rooted product. Wn∘K2. is given as(47)τWn∘K2=3+52n+3−52n−2.Proof.
Consider the networkWn∘K2 with VWn∘K2=2n+1 and EWn∘K2=3n. The general formation is shown in Figure 8.
Applying Lemma1, we have(48)τWn∘K2=12n+12det2n+1I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of the network Wn∘K2, respectively.(49)=12n+12detn+1111…111000…0001211…111011…1111121…111101…1111112…111110…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮1111…211111…0111111…121111…1011111…112111…1100011…111501…1100101…111050…1110110…111105…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0111…011111…5010111…101111…0500111…110011…1052n+1×2n+1=det100…000−100…000010…0000−10…000001…00000−1…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…100000…−100000…010000…0−10000…001000…00−1−100…0004−10…00−10−10…000−14−1…00000−1…0000−14…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…−100000…4−10000…0−10000…−14−1000…00−1−100…0−142n×2n⇒τWn∘K2=detPn×nQn×nRn×nSn×n2n×2n.
By using Lemma4, we obtain(50)τWn∘K2=detP⋅detS−RP−1Q=1⋅det3−100…000−1−13−10…00000−13−1…000000−13…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…3−1000000…−13−100000…0−13−1−1000…00−13n×n.
Using Lemma2,(51)=2Tn32−1⇒τWn∘K2=3+52n+3−52n−2.Figure 8
The general formation of the rooted productWn∘K2.Definition 5.
The vertex semitotal networkRΓ of a network Γ is obtained by taking a vertex corresponding to each edge of Γ and then by joining these new vertices to the end points of their corresponding edges.Theorem 9.
For alln, the complexity of the vertex semitotal network RSn is given as(52)τRSn=3n.Proof.
Consider the vertex semitotal networkRSn with VRSn=2n+1 and ERSn=3n, see Figure 9 for its general formation.
Applying Lemma1, we have(53)τRSn=12n+12det2n+1I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of RSn, respectively.(54)=12n+12det2n+1000…000000…0000311…111011…1110131…111101…1110113…111110…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0111…311111…0110111…131111…1010111…113111…1100011…111311…1110101…111131…1110110…111113…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0111…011111…3110111…101111…1310111…110111…1132n+1×2n+1=det200…000−100…000020…0000−10…000002…00000−1…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…200000…−100000…020000…0−10000…002000…00−1−100…000200…0000−10…000020…00000−1…000002…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…−100000…200000…0−10000…020000…00−1000…0022n×2n⇒τRSn=detPn×nQn×nRn×nSn×n2n×2n.
By using Lemma4, we obtain(55)τRSn=detP⋅detS−RP−1Q=2n.det32000…000003200…000000320…000000032…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…320000000…032000000…003200000…00032n×n.
Using Lemma2,(56)=2n32n⇒τRSn=3n.Figure 9
The vertex-semitotal networkRSn.Definition 6.
The edge semitotal networkQΓ of the network Γ is obtained by inserting a vertex on each edge of Γ and then by joining those new vertices that share common edges in the network Γ.Theorem 10.
For alln, the complexity of the edge-semitotal network QSn is given as(57)τQSn=−1n+1−n−1n−1.Proof.
Consider the networkQSn with VQSn=2n+1 and EQSn=2n+n2, see the general form in Figure 10.
Applying Lemma1, we have(58)τQSn=12n+12det2n+1I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of QSn, respectively.(59)=12n+12detn+1111…111000…0001211…111011…1111121…111101…1111112…111110…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮1111…211111…0111111…121111…1011111…112111…1100011…111n+200…0000101…1110n+20…0000110…11100n+2…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0111…011000…n+2000111…101000…0n+200111…110000…00n+22n+1×2n+1=det100…000−100…000010…0000−10…000001…00000−1…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…100000…−100000…010000…0−10000…001000…00−1−100…000n+1−1−1…−1−1−10−10…000−1n+1−1…−1−1−100−1…000−1−1n+1…−1−1−1⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…−100−1−1−1…n+1−1−1000…0−10−1−1−1…−1n+1−1000…00−1−1−1−1…−1−1n+12n×2n⇒τQSn=detPn×nQn×nRn×nSn×n2n×2n.
By using Lemma4, we obtain(60)τQSn=detP.detS−RP−1Q=1n−1ndet−n111…11111−n11…111111−n1…1111111−n…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…−n1111111…1−n111111…11−n11111…111−nn×n.
Using Lemma2,(61)=−1n−n+n−1−n−1n−1⇒τQSn=−1n+1−n−1n−1.Figure 10
The edge-semitotal networkQSn.Theorem 11.
For alln≥3, the complexity of the network Cn∘K2+K1 is given as(62)τCn∘K2+K1=2n7+334n+7−334n−2,where Cn∘K2 represents the rooted product of Cn and K2.Proof.
Consider the networkCn∘K2+K1 with VCn∘K2+K1=2n+1 and ECn∘K2+K1=4n, see the general form in Figure 11.
Applying Lemma1, we have(63)τCn∘K2+K1=12n+12det2n+1I−D¯+A¯,where D¯ and A¯ represent the degree and adjacency matrices of Cn∘K2+K1, respectively.(64)=12n+12det2n+1000…000000…0000501…110011…1110050…111101…1110105…111110…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0111…501111…0110111…050111…1010011…105111…1100011…111311…1110101…111131…1110110…111113…111⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0111…011111…3110111…101111…1310111…110111…1132n+1×2n+1=det4−10…00−1−100…000−14−1…0000−10…0000−14…00000−1…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…4−10000…−100000…−14−1000…0−10−100…0−14000…00−1−100…000200…0000−10…000020…00000−1…000002…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…−100000…200000…0−10000…020000…00−1000…0022n×2n⇒τCn∘K2+K1=detPn×nQn×nRn×nSn×n2n×2n.
By using Lemma4, we obtain(65)τCn°K2+K1=detP.detS−RP−1Q=2ndet72−100…000−1−172−10…00000−172−1…000000−172…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…72−1000000…−172−100000…0−172−1−1000…00−172n×n.
Using Lemma2,(66)=2n.2Tn74−1⇒τCn∘K2+K1=2n7+334n+7−334n−2.Figure 11
The general formation of the networkCn∘K2+K1.


## 3. Synopsis and 3D Comparison of the Complexities of the Networks

This section comprises a tabular summary and 3D graphical plots and comparison of the closed formulae for the complexities of networks calculated in this article :(i)
Table1 indicates a brief summary of our findings in the form of complexity of various networks and also categorizes the network being planar or nonplanar(ii)
Figure12 shows the individual 3D graphical tends of the values of the complexity of networks discussed in this article, whereas Figure 13 reveals the relative comparison of the values of the complexity of these networks, reveling the golden one to be the dominated layer among allTable 1
Synopsis of the main findings.
NetworkParametersComplexityPlanar vs. nonplanarSn+W3∀n∈ℕ5n−1n+54NonplanarD2Sn∀n∈ℕn⋅22nPlanarS′Sn∀n∈ℕn⋅2n−1PlanarSn⊠P2∀n∈ℕ8nn+1PlanarV′Sn∀n∈ℕnnn+1n−1NonplanarSn+K2∀n∈ℕ3n−22n+62−n+32PlanarWn′n≥322n−2n+1+1PlanarWn∘P2n≥33+5/2n+3−5/2n−2PlanarRSn∀n∈ℕ3nPlanarQSn∀n∈ℕ−1n+1−n−1n−1NonplanarCn∘P2+K1∀n∈ℕ2n7+33/4n+7−33/4n−2NonplanarFigure 12
Graphical behaviors of the complexities of the networksWn′⟶ (a), D2Sn⟶ (b), Sn⊠P2⟶ (c), Wn∘P2⟶ (d), QSn⟶ (e), Sn+K2⟶ (f), V′Sn⟶ (g), S′Sn⟶ (h), Sn+W3⟶ (i), RSn⟶ (j), and Cn∘P2+K1⟶ (k).
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)Figure 13
Graphical comparison of the complexities of the networks.


## 4. Conclusion

The complexity, i.e., number of spanning trees, of a network is a purposeful algebraic invariant. The calculation of this measurement gives an important information about the reliability of a network by providing the information of total number of acyclic networks present within. In this article, we have computed the complexity of networks operation such asWn′, D2Sn, Sn⊠P2, Wn∘P2, QSn, Sn+K2, V′Sn, S′Sn, Sn+W3, RSn, and Cn∘P2+K1. Mainly, our techniques have been algebraic and involve Chebyshev polynomials and concepts of the matrix theory while calculating our results.



---

*Source: 9999157-2021-07-13.xml*