# Computation of the Complexity of Networks under Generalized Operations

Authors: Hafiz Usman Afzal; Muhammad Javaid; Ali Ovais; Md Nur Alam
Journal: Complexity
 (2022)

---

## Abstract

The connected and acyclic components contained in a network are identified by the computation of its complexity, where complexity of a network refers to the total number of spanning trees present within. The article in hand deals with the enumeration of the complexity of various networks’ operations such as sum (K2,n+W3, K2,n+nK1, Kn+Sn), product (K2,n⊠K2, K2,n⋉K2, Kn×K2, Kn⊠K2), difference K2,n⊖K2, and the conjunction of Sn with K2. All our computations have been concluded by implementation of the methods of linear algebra and matrix theory. Our derivations will also be highlighted with the assistance of 3D plots at the end of this article.


---

## Body

## 1. Introduction

Only simple networkG=VG,EG shall be dealt with throughout the paper. One of the most useful algebraic invariants is the complexity, i.e., number of spanning trees in a network admitting roots in combinatorics, algebraic graph theory, and networking. It is prominently linked with network engineering and particular branches of computer sciences that deal in the security designs specifically. Realistically, concreteness and precision in a network are based on the number of spanning trees it possesses. This indicates that complexity is an identifier for the quality of a network. Certain applications of complexity in different fields of mathematics and physics can be observed in [1–4]. For instance, we are living in an era of networking. The tools similar to complexity ensure the robustness and accuracy in a network so that one can obtain interruption free signals, since the complexity is an identifier of the number of connected and acyclic pathways present in a network, where every such pathway contains all junctions or vertices present in a network. So, this invariant helps in the enhancement of robustness of wireless sensor networks (WSNs) and other similar mobile networks by relating the total number of spanning trees present within. Another application of complexity can be observed in the security design of a sensitive area of a building. Say there are several secured chambers, and there are legitimate passages only to reach to those chambers. One legitimate passage can be identified by a unique pathway. That is, no cyclic pathway is allowed from one chamber to another. A programming-based software application will ensure if a visitor follows a legitimate passage or not through acyclic pathway mechanism, whereas such unique acyclic pathway is termed as complexity of the network.


### 1.1. Definitions and Preliminaries

The following lemma is a direct derivation of Temperley’s equation mentioned previously.Lemma 1 (see [5]).
LetGbeϱorder network; then,(1)τG=1ϱ2detϱI−DG¯+AG¯,where G¯≅G.The above expression is more useful as it represents the complexity ofG as the determinant of a particular matrix, rather than involving its eigenvalues. The eigenvalues based process is relatively difficult and complex.The solution of the following iterative expression defines the first kind of Chebyshev polynomials.(2)Tϱ+1x−2xTϱx+Tϱ−1x=0;T0x=1,T1x=x.The standard solution of (2) gives(3)Tϱx=12x+x2−1ϱ+x−x2−1ϱ;ϱ≥1.The solution of the following iterative expression defines the second kind of Chebyshev polynomials.(4)Uϱ+1x−2xUϱx+Uϱ−1x=0;U0x=1,U1x=x.The standard solution of (4) gives(5)Umz=12z2−1z+z2−1ϱ+1−z−z2−1ϱ+1;ϱ≥1.Identity (4) is valid ∀z∈ℂ excluding z=±1 [6]. The determinants are closely related to both 1st and 2nd kind Chebyshev Polynomials.where H1 and H2 are non-singular matrices.Lemma 2 (see [7, 8]).
(i)
∀ϕ≥3, detAmϕ=2Tmϕ/2−1, where(6)Amϕ=ϕ−100…000−1−1ϕ−10…00000−1ϕ−1…000000−1ϕ…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…ϕ−1000000…−1ϕ−100000…0−1ϕ−1−1000…00−1ϕ.(i)
∀ϕ≥4, m≥3, detBmϕ=2ϕ+m−3/ϕ−3Tmϕ−1/2−1, where(7)Bmϕ=ϕ011…11100ϕ01…111110ϕ0…1111110ϕ…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…ϕ0111111…0ϕ011111…10ϕ00111…110ϕ.(i)
∀m,ϕ, detℂmϕ=ϕ−1Um−1ϕ+1/2, where(8)ℂmϕ=ϕ−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ϕ.(i)
∀ϕ≥2, m≥3, detDmϕ=m+ϕ−2Um−1ϕ/2, where(9)Dmϕ=ϕ011…11110ϕ+101…111110ϕ+10…1111110ϕ+1…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…ϕ+10111111…0ϕ+1011111…10ϕ+101111…110ϕ.Lemma 3 (see [9]).
∀ϕandm, detWmϕ=ϕ+m−1ϕ−1m−1, whereWmϕis anm×mcirculant matrix given as(10)Wmϕ=ϕ111…11111ϕ11…111111ϕ1…1111111ϕ…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…ϕ1111111…1ϕ111111…11ϕ11111…111ϕ.Lemma 4 (see [10]).
LetH1, H2, H3, andH4be the block matrices of ordersθ×θ, θ×ϑ, ϑ×θ, andϑ×ϑ, respectively. Then,(11)detH1H2H3H4=detH4−H3H1−1H2×detH1=detH1−H2H4−1H3×detH4,Lemma 5 (see [11]).
Forϕ≥5, let us consider a circulant matrix given as(12)Eϕ=ζη10…001ηηζη1…00011ηζη…000001ηζ…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…ζη100000…ηζη11000…1ηζηη100…01ηζϕ×ϕ,(13)τEϕ=ζ2+4ζ−η2+1∏i=1ϕ2−1ζ+2ηcos2πiϕ+2cos4πiϕ2:for evenϕ;ζ+2η+1∏i=1ϕ2ζ+2ηcos2πiϕ+2cos4πiϕ2:for oddϕ.We shall also provide a few definitions [12, 13] in Section 3 before a certain result, where necessary. Throughout the article, G¯ represents the complement of the network G.


### 1.2. Main Contributions

In the present article, we will mainly compute the closed formulae for the complexity of various generalized operations on graphs such as sum (K2,n+W3, K2,n+nK1, Kn+Sn), product (K2,n⊠K2, K2,n⋉K2, Kn×K2, Kn⊠K2), difference K2,n⊖K2, and the conjunction of Sn with K2. Furthermore, all our computations have been concluded by implementation of the methods of linear algebra and matrix theory.


### 1.3. Main Structure

The main structure of this article is as follows:1.
Section1 comprises the introduction and preliminaries of our main work.2.
Section2 contains the salient work related to our derivations.3.
Section3 consists of the main derivations we have obtained in the form of the complexities of various networks’ operations.4.
Section4 contains a brief summary and graphical illustrations of our work.5.
Section5 gives the conclusion and also tells about the future work related to this paper.


## 1.1. Definitions and Preliminaries

The following lemma is a direct derivation of Temperley’s equation mentioned previously.Lemma 1 (see [5]).
LetGbeϱorder network; then,(1)τG=1ϱ2detϱI−DG¯+AG¯,where G¯≅G.The above expression is more useful as it represents the complexity ofG as the determinant of a particular matrix, rather than involving its eigenvalues. The eigenvalues based process is relatively difficult and complex.The solution of the following iterative expression defines the first kind of Chebyshev polynomials.(2)Tϱ+1x−2xTϱx+Tϱ−1x=0;T0x=1,T1x=x.The standard solution of (2) gives(3)Tϱx=12x+x2−1ϱ+x−x2−1ϱ;ϱ≥1.The solution of the following iterative expression defines the second kind of Chebyshev polynomials.(4)Uϱ+1x−2xUϱx+Uϱ−1x=0;U0x=1,U1x=x.The standard solution of (4) gives(5)Umz=12z2−1z+z2−1ϱ+1−z−z2−1ϱ+1;ϱ≥1.Identity (4) is valid ∀z∈ℂ excluding z=±1 [6]. The determinants are closely related to both 1st and 2nd kind Chebyshev Polynomials.where H1 and H2 are non-singular matrices.Lemma 2 (see [7, 8]).
(i)
∀ϕ≥3, detAmϕ=2Tmϕ/2−1, where(6)Amϕ=ϕ−100…000−1−1ϕ−10…00000−1ϕ−1…000000−1ϕ…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…ϕ−1000000…−1ϕ−100000…0−1ϕ−1−1000…00−1ϕ.(i)
∀ϕ≥4, m≥3, detBmϕ=2ϕ+m−3/ϕ−3Tmϕ−1/2−1, where(7)Bmϕ=ϕ011…11100ϕ01…111110ϕ0…1111110ϕ…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…ϕ0111111…0ϕ011111…10ϕ00111…110ϕ.(i)
∀m,ϕ, detℂmϕ=ϕ−1Um−1ϕ+1/2, where(8)ℂmϕ=ϕ−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ϕ.(i)
∀ϕ≥2, m≥3, detDmϕ=m+ϕ−2Um−1ϕ/2, where(9)Dmϕ=ϕ011…11110ϕ+101…111110ϕ+10…1111110ϕ+1…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…ϕ+10111111…0ϕ+1011111…10ϕ+101111…110ϕ.Lemma 3 (see [9]).
∀ϕandm, detWmϕ=ϕ+m−1ϕ−1m−1, whereWmϕis anm×mcirculant matrix given as(10)Wmϕ=ϕ111…11111ϕ11…111111ϕ1…1111111ϕ…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…ϕ1111111…1ϕ111111…11ϕ11111…111ϕ.Lemma 4 (see [10]).
LetH1, H2, H3, andH4be the block matrices of ordersθ×θ, θ×ϑ, ϑ×θ, andϑ×ϑ, respectively. Then,(11)detH1H2H3H4=detH4−H3H1−1H2×detH1=detH1−H2H4−1H3×detH4,Lemma 5 (see [11]).
Forϕ≥5, let us consider a circulant matrix given as(12)Eϕ=ζη10…001ηηζη1…00011ηζη…000001ηζ…0000⋮⋮⋮⋮⋱⋮⋮⋮⋮0000…ζη100000…ηζη11000…1ηζηη100…01ηζϕ×ϕ,(13)τEϕ=ζ2+4ζ−η2+1∏i=1ϕ2−1ζ+2ηcos2πiϕ+2cos4πiϕ2:for evenϕ;ζ+2η+1∏i=1ϕ2ζ+2ηcos2πiϕ+2cos4πiϕ2:for oddϕ.We shall also provide a few definitions [12, 13] in Section 3 before a certain result, where necessary. Throughout the article, G¯ represents the complement of the network G.


## 1.2. Main Contributions

In the present article, we will mainly compute the closed formulae for the complexity of various generalized operations on graphs such as sum (K2,n+W3, K2,n+nK1, Kn+Sn), product (K2,n⊠K2, K2,n⋉K2, Kn×K2, Kn⊠K2), difference K2,n⊖K2, and the conjunction of Sn with K2. Furthermore, all our computations have been concluded by implementation of the methods of linear algebra and matrix theory.


## 1.3. Main Structure

The main structure of this article is as follows:1.
Section1 comprises the introduction and preliminaries of our main work.2.
Section2 contains the salient work related to our derivations.3.
Section3 consists of the main derivations we have obtained in the form of the complexities of various networks’ operations.4.
Section4 contains a brief summary and graphical illustrations of our work.5.
Section5 gives the conclusion and also tells about the future work related to this paper.


## 2. Related Work

If we talk about the closed formulae for the complexity of an infinite family of networks, we shall not be able to locate any such generalized result. Although it is still possible to derive the new closed formulae of the complexity of classes of networks having orderm, where m is sufficiently large, it is useful to obtain this invariant for the networks of finite order for the values as we increase the order of a network. If we look into the historical development of this concept, the calculation of the complexity of the complete network as τKβ=ββ−2 is the foremost concept that appeared in [14]. The second prominent result in this regard is the complexity of the complete bipartite network which is again derived by Cayley [14] as τKμ,ν=μν−1νμ−1. In [15], the closed formula for the complexity of Mobius ladder has been obtained as τMχ=χ/22+3χ+2−χχ+2 for χ≥2 in [15].The determination of the total spanning trees of a network has recently reappeared as an active topic. Kirchhoff’s matrix tree theorem [16] is a prominent result in this regard. It represents the complexity of a network as the determinant of a random cofactor of its Kirchhoff’s matrix, where, say for a network G, KG=degree matrix ofG−adjacency matrix ofG indicates its Kirchhoff’s matrix.A combinatorial method for computing the complexity of a network is with the use of contraction-deletion theorem. As an iterative process for an edgeuv∈EG, the complexity of G is the sum of τG|uv and τG−uv. Here, G|uv is the network derived as the result of contraction of uv in G repeatedly until the end points u and v coincide [17].In [18], the self-adapted task scheduling strategies in the wireless sensor networks have been designed and analyzed. Wang et al. [19] discussed the ant colony optimization-based location-aware routing for wireless sensor networks. In [20], a pedestrian detection method has been designed and examined based on the genetic algorithm for optimizing XGBoost training parameters. For wireless sensor networks, Wan and Xiong designed and assessed an energy-efficient sleep scheduling mechanism with similarity measure [21]. Lu et al. in [22] explored a finger vein-based personal authentication mechanism for Internet-related security. Furthermore, in [23, 24], some latest work on the enumeration of the complexity of networks can be observed.


## 3. Main Results

In networking, the characteristic of developing new structures from the existing ones through network operations and studying their various properties always remains active. The present section addresses our main derivations consisting of the closed formulae of the complexity of various networks obtained as the result of network operations.Theorem 1.
For alln, the complexity of the networkK2,n+W3is given by(14)τK2,n+W3=6n−1n+4n+64.Proof.
Consider the networkK2,n+W3 with VK2,n+W3=n+6 and EK2,n+W3=6n+14 (see the general formation in Figure 1).
Applying Lemma1, we have(15)τK2,n+W3=1n+62detn+6I−D¯+A¯=1n+62detn+6000000000…00000n+600000000…000000n+60000000…0000000n+6000000…00000000n+510000…000000001n+50000…00000000007111…11110000001711…11110000001171…11110000001117…1111⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮0000001111…71110000001111…17110000001111…11710000001111…1117n+6×n+6.
Now on the above determinant, we perform the following operations simultaneously:(i)
Adding all columns toC1.(ii)
From C1, we take the number n+5 as common.(iii)
SubtractingC1 from all columns.(iv)
Expanding alongR1.
This yields(16)=detn+5−1−1−1−1−1−1−1−1…−1−1−1−1−1n+5−1−1−1−1−1−1−1…−1−1−1−1−1−1n+5−1−1−1−1−1−1…−1−1−1−1−1−1−1n+40−1−1−1−1…−1−1−1−1−1−1−10n+4−1−1−1−1…−1−1−1−1−1−1−1−1−16000…0000−1−1−1−1−10600…0000−1−1−1−1−10060…0000−1−1−1−1−10006…0000⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮−1−1−1−1−10000…6000−1−1−1−1−10000…0600−1−1−1−1−10000…0060−1−1−1−1−10000…0006n+5×n+5,⇒τK2,n+W3=detP5×5Q5×nRn×5Sn×nn+5×n+5.
By using Lemma4, we get(17)τK2,n+W3=detS.detP−QS−1R=6n165−15det−5n−30n+6n+6n+6n+6n+6−5n−30n+6n+6n+6n+6n+6−5n−30n+6n+6n+6n+6n+6−5n−24nn+6n+6n+6n−5n−24.
Evaluating and simplifying, we obtainτK2,n+W3=6n−1n+4n+64.Figure 1
The networkK2,n+W3.Theorem 2.
For alln, the complexity of the strong productK2,n⊠K2is given by(18)τK2,n⊠K2=24n2n3+2n2+n.Proof.
Consider the networkK2,nK2 with VK2,nK2=2n+4 and EK2,nK2=9n+2 (see the general formation in Figure 2).
Applying Lemma1, we have(19)τK2,n⊠K2=12n+42det2n+4I−D¯+A¯=1n+62detn+6000000000…00000n+600000000…000000n+60000000…0000000n+6000000…00000000n+510000…000000001n+50000…00000000007111…11110000001711…11110000001171…11110000001117…1111⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮0000001111…71110000001111…17110000001111…11710000001111…1117n+6×n+6=detn+5−1−1−1−1−1−1−1−1…−1−1−1−1−1n+5−1−1−1−1−1−1−1…−1−1−1−1−1−1n+5−1−1−1−1−1−1…−1−1−1−1−1−1−1n+40−1−1−1−1…−1−1−1−1−1−1−10n+4−1−1−1−1…−1−1−1−1−1−1−1−1−16000…0000−1−1−1−1−10600…0000−1−1−1−1−10060…0000−1−1−1−1−10006…0000⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮−1−1−1−1−10000…6000−1−1−1−1−10000…0600−1−1−1−1−10000…0060−1−1−1−1−10000…0006n+5×n+5,⇒τK2,n⊠K2=detP3×3Q3×2nR2n×3S2n×2n2n+3×2n+3.
By using Lemma4, we get(20)τK2,n⊠K2=detS.detP−QS−1R=5n245ndet3n+22−n2−n−22−n23n+22−n2−n−22−n23n+22.
Evaluating the above determinant, we obtain finally⇒τK2,n⊠K2=24n2n3+2n2+n.Figure 2
The strong productK2,n⊠K2.Theorem 3.
For alln, the complexity of the homomorphic productK2,n⋉K2≅K2,n×K2is given by(21)τK2,n⋉K2=8n−1n3+6n2+8n.Proof.
Consider the networkK2,n⋉K2 with VK2,n⋉K2=2n+4 and EK2,n⋉K2=5n+2 (see the general formation in Figure 3).
Applying Lemma1, we have(22)τK2,n⋉K2=12n+42det2n+4I−D¯+A¯=detn+5−1−1−1−1−1−1−1−1…−1−1−1−1−1n+5−1−1−1−1−1−1−1…−1−1−1−1−1−1n+5−1−1−1−1−1−1…−1−1−1−1−1−1−1n+40−1−1−1−1…−1−1−1−1−1−1−10n+4−1−1−1−1…−1−1−1−1−1−1−1−1−16000…0000−1−1−1−1−10600…0000−1−1−1−1−10060…0000−1−1−1−1−10006…0000⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮−1−1−1−1−10000…6000−1−1−1−1−10000…0600−1−1−1−1−10000…0060−1−1−1−1−10000…0006n+5×n+5=6n165−15det−5n−30n+6n+6n+6n+6n+6−5n−30n+6n+6n+6n+6n+6−5n−30n+6n+6n+6n+6n+6−5n−24nn+6n+6n+6n−5n−24,⇒τK2,n<imesK2=detP3×3Q3×2nR2n×3S2n×2n2n+3×2n+3.
By using Lemma4, we get(23)τK2,n⋉K2=detS.detP−QS−1R=8n183det5n+8−n−n−8−n5n+8−3n−n−8−3n5n+8.
Evaluating the above determinant and simplifying, we obtain finally⇒τK2,n⋉K2=8n−1n3+6n2+8n.Figure 3
The homomorphic productK2,n⋉K2.Theorem 4.
For alln, the complexity of the mirror networkK2,n+nK1is given as(24)τK2,n+nK1=4nn+1n+22n−2.Proof.
Consider the networkK2,n+nK1 with VK2,n+nK1=2n+2 and EK2,n+nK1=n2+4n (see Figure 4).
Applying Lemma1, we have(25)τK2,n+nK1=12n+22det2n+2I−D¯+A¯=12n+22det2n+11000…000000…00012n+1000…000000…00000n+311…111000…000001n+31…111000…0000011n+3…111000…000⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00111…n+311000…00000111…1n+31000…00000111…11n+3000…00000000…000n+311…11100000…0001n+31…11100000…00011n+3…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00000…000111…n+31100000…000111…1n+3100000…000111…11n+3=det2n−1−1−1…−1−1−1−1−1−1…−1−1−1−1n+200…000−1−1−1…−1−1−1−10n+20…000−1−1−1…−1−1−1−100n+2…000−1−1−1…−1−1−1⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1000…n+200−1−1−1…−1−1−1−1000…0n+20−1−1−1…−1−1−1−1000…00n+2−1−1−1…−1−1−1−1−1−1−1…−1−1−1n+200…000−1−1−1−1…−1−1−10n+20…000−1−1−1−1…−1−1−100n+2…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1−1−1−1…−1−1−1000…n+200−1−1−1−1…−1−1−1000…0n+20−1−1−1−1…−1−1−1000…00n+22n+1×2n+1,⇒τK2,n+nK1=detP1×1Q1×2nR2n×1S2n×2n2n+1×2n+1.
By using Lemma4, we have(26)τK2,n+nK1=detS.detP−QS−1R=3n×det2n+33−n3−n32n+33.
Simplification finally givesτK2,n+nK1=4nn+1n+22n−2.Figure 4
The networkK2,n+nK1.Theorem 5.
For alln, the complexity of the cartesian productKn×K2is given as(27)τKn×K2=nn−2n+2n−1.Proof.
Consider thenetworkKn×K2 with VKn×K2=2n and EKn×K2=n2 (see Figure 5).
Applying Lemma1, we have(28)τKn×K2=12n2det2nI−D¯+A¯=12n2detn+100…000011…1110n+10…000101…11100n+1…000110…111⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…n+100111…011000…0n+10111…101000…00n+1111…110011…111n+100…000101…1110n+10…000110…11100n+1…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮111…011000…n+100111…101000…0n+10111…110000…00n+12n×2n,⇒τKn×K2=12n2detPn×nQn×nRn×nSn×n2n×2n.
By using Lemma4, we have(29)τKn×K2=12n2detS.detP−QS−1R=12n2×detn2+n+22−n111n2+n+22−n111n2+n+22−n.
Simplifying, we getτKn×K2=nn−2n+2n−1.Figure 5
The Cartesian productKn×K2.Corollary 1.
For alln, the complexity of the symmetric differenceKn⊖K2is given as(30)τKn⊖K2=nn−2n+2n−1.Proof.
SinceKn×K2≅Kn⊖K2 (see Figure 6), τKn⊖K2=nn−2n+2n−1=τKn×K2.Figure 6
The symmetric differenceKn⊖K2.Theorem 6.
For alln, the complexity of the strong productKn⊠K2≅Kn+Knis given as(31)τKn⊠K2=2n2n−2.Proof.
Consider the networkKn⊠K2 with VKn⊠K2=2n and EKn⊠K2=n2n−1 (see Figure 7).
Applying Lemma1, we have(32)τKn⊠K2=12n2det2nI−D¯+A¯=12n2det2n00…000000…00002n0…000000…000002n…000000…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…2n00000…000000…02n0000…000000…002n000…000000…0002n00…000000…00002n0…000000…000002n…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…000000…2n00000…000000…02n0000…000000…002n2n×2n,⇒τKn⊠K2=12n2detPn×nOn×nOn×nSn×n2n×2n,⇒τKn⊠K2=12n22n2n.
Simplifying, we getτKn⊠K2=2n2n−2.Figure 7
The strong productKn⊠K2.Theorem 7.
For alln, the complexity of the symmetric differenceK2,n⊖K2is given by(33)τK2,n⊖K2=n+22n+2.Proof.
Consider the networkK2,n⊖K2 with VK2,n⊖K2=2n+4 and EK2,n⊖K2=n2+4n+4 (see the general formation in Figure 8).
Applying Lemma1, we have(34)τK2,n⊖K2=12n+42det2n+4I−D¯+A¯=12n2det2n00…000000…00002n0…000000…000002n…000000…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…2n00000…000000…02n0000…000000…002n000…000000…0002n00…000000…00002n0…000000…000002n…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…000000…2n00000…000000…02n0000…000000…002n2n×2n,⇒τKn⊠K2=12n2detPn×nOn×nOn×nSn×n2n×2n,⇒τK2,n⊖K2=detP3×3Q3×2nR2n×3S2n×2n2n+3×2n+3.
By using Lemma4, we get(35)τK2,n⊖K2=detP.detS−RP−1Q=n+22n+14n2+3n+2×n+24n+4det3n+4−n−2−n−2−n−23n+4−n−n−2−n3n+4.
Evaluating the determinant and simplifying, we obtain finally⇒τK2,n⊖K2=n+22n+2.Figure 8
The symmetric differenceK2,n⊖K2.Theorem 8.
For alln, the complexity of the networkKn+Snis given by(36)τKn+Sn=2n+1nn+1n−1.Proof.
Consider the networkKn+Sn with VKn+Sn=2n+1 and EKn+Sn=3n/2n+1. Applying Lemma 1, we have(37)τKn+Sn=12n+12det2n+1I−D¯+A¯=12n+12det2n+1000…000000…0000n+211…111000…00001n+21…111000…000011n+2…111000…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0111…n+211000…0000111…1n+21000…0000111…11n+2000…0000000…0002n+100…0000000…00002n+10…0000000…000002n+1…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0000…000000…2n+1000000…000000…02n+100000…000000…002n+1=detn+100…000−1−1−1…−1−1−10n+10…000−1−1−1…−1−1−100n+1…000−1−1−1…−1−1−1⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮000…n+100−1−1−1…−1−1−1000…0n+10−1−1−1…−1−1−1000…00n+1−1−1−1…−1−1−1−1−1−1…−1−1−12n00…000−1−1−1…−1−1−102n0…000−1−1−1…−1−1−1002n…000⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1−1−1…−1−1−1000…2n00−1−1−1…−1−1−1000…02n0−1−1−1…−1−1−1000…002n2n×2n,⇒τKn+Sn=detPn×nQn×nRn×nSn×n2n×2n.
By using Lemma4, we obtain(38)τKn+Sn=detS.detP−QS−1R=n+1n×−2n+1n+1ndet−n111…1111−n11…111111−n1…1111111−n…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…−n1111111…1−n111111…11−n11111…111−nn×n.
Using Lemma3 and simplifying, we get ⇒τKn+Sn=2n+1nn+1n−1.Theorem 9.
For alln, the complexity of the conjunctionSn∧K2is given as(39)τSn∧K2=4n+12n+22n−2.Proof.
Consider the networkSn∧K2 with VSn∧K2=2n+2 and ESn∧K2=n2+4n+1 (see Figure 9).
Applying Lemma1, we have(40)τSn∧K2=12n+22det2n+2I−D¯+A¯=12n+22det2n+20000…000000…00002n+2000…000000…00000n+311…111000…000001n+31…111000…0000011n+3…111000…000⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00111…n+311000…00000111…1n+31000…00000111…11n+3000…00000000…000n+311…11100000…0001n+31…11100000…00011n+3…111⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮00000…000111…n+31100000…000111…1n+3100000…000111…11n+3=det2n+1−1−1−1…−1−1−1−1−1−1…−1−1−1−1n+200…000−1−1−1…−1−1−1−10n+20…000−1−1−1…−1−1−1−100n+2…000−1−1−1…−1−1−1⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1000…n+200−1−1−1…−1−1−1−1000…0n+20−1−1−1…−1−1−1−1000…00n+2−1−1−1…−1−1−1−1−1−1−1…−1−1−1n+200…000−1−1−1−1…−1−1−10n+20…000−1−1−1−1…−1−1−100n+2…000⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮−1−1−1−1…−1−1−1000…n+200−1−1−1−1…−1−1−1000…0n+20−1−1−1−1…−1−1−1000…00n+22n+1×2n+1,⇒τSn∧K2=detP1×1Q1×2nR2n×1S2n×2n2n+1×2n+1.
By using Lemma4, we have(41)τSn∧K2=detS.detP−QS−1R=−nnn+2×detn2+3n+4−n111…1111n2+3n+4−n11…111111n2+3n+4−n1…1111111n2+3n+4−n…1111⋮⋮⋮⋮⋱⋮⋮⋮⋮1111…n2+3n+4−n1111111…1n2+3n+4−n111111…11n2+3n+4−n11111…111n2+3n+4−nn×n×det2n+1−n.
Lemma3 and simplification finally give(42)τSn∧K2=4n+12n+22n−2.Figure 9
The disjunction networkSn∧K2.


## 4. Synopsis and the Diagrammatic Comparison of the Complexities of the Networks Obtained

This section consists of a briefing and graphical plots and juxtaposition of the values of complexities of the networks enumerated in this note.Table1 indicates a synopsis of our results in the shape of complexities of various networks and also categorically recognizes it being planar or not.Table 1
Synopsis of the results.
NetworkParametersComplexityPlanar∨ non-planarK2,n+W3∀n∈ℕ6n−1n+4n+64Non-planarK2,n⊠K2∀n∈ℕ24n2n3+2n2+nNon-planarK2,n⋉K2∀n∈ℕ8n−1n3+6n2+8nNon-planarK2,n+nK1∀n∈ℕ4nn+1n+22n−2Non-planarKn×K2∀n∈ℕnn−2n+2n−1Non-planarKn⊠K2∀n∈ℕ2n2n−2Non-planarK2,n⊖K2∀n∈ℕn+22n+2Non-planarKn+Sn∀n∈ℕ2n+1nn+1n−1Non-planarSn∧K2∀n∈ℕ4n+12n+22n−2Non-planarFigure10 shows the discrete graphical shapes of the values of the complexity of networks obtained here, whereas Figure 11 addresses the relative comparison of the complexities of these networks, revealing the red one to be the dominating layer.Figure 10
Trends of the enumerated complexities ofK2,n+W3⟶T1, K2,n⊠K2⟶T2, K2,n⋉K2⟶T3, K2,n+nK1⟶T4, Kn×K2⟶T5, Kn⊠K2⟶T6, K2,n⊖K2⟶T7, Kn+Sn⟶T8, and Sn∧K2⟶T9.Figure 11
Comparison of the trends of the enumerated complexities.


## 5. Conclusion

One of the meaningful algebraic invariants in networking nowadays is complexity. This invariant provides us the information of the total number of acyclic networks present within the base network, which ultimately ensures the reliability and accuracy in the network. We have enumerated here the complexity of various operations on networks such asK2,n+W3, K2,n⊠K2, K2,n⋉K2, K2,n+nK1, Kn×K2, Kn⊠K2, K2,n⊖K2, Kn+Sn, and Sn∧K2. The adopted methods are mainly algebraic and feature Chebyshev polynomials and the matrix theory in the calculations. As future work, we encourage the researchers to obtain the complexities of further generalized operations on networks such as corona product, zig zag product, homomorphic product, join, shadow, conjunction, and disjunction of various classes of networks.



---

*Source: 6288054-2022-09-08.xml*