Spectrum of prism graph and relation with network related quantities

1.   Introduction

Visualization and network analysis of real world networks including social networks, worldwide web, internet and biological networks is effectual research field during recent years ^[1,2]. Subjects of control theory nonlinear dynamics, and graph theory are utilized in study of complex networks which makes it more challenging and comprehensive. Depending upon the structural characterization, eigenvalues of a network graph contravene in robustness analysis, electrical networks and vibration theory explains the strength and stability of these networks ^[3,4]. Modern Scientific fields like theoretical chemistry, communication networks and combinatorial optimization are extensively utilizing numerous distance and degree based eigenvalues ^[8,9]. The undirected graphs are used to describe different complex networks and models whereas processors and communication links are represented by vertices and edges, respectively. Consider a graph G whose vertices are labeled as $1, 2, 3, ..., n$ then its adjacency matrix $\mathcal{A}(G)$ is defined as

In algebraic graph theory, adjacency matrix has numerous implementations i.e., widely used in computer programs as data structure for representation and manipulating the graphs due to their less storage and faster compilation capability ^[10,11,12]. The eigenvalues of matrix $\mathcal{A}(G)$ are considered as eigenvalues of given graph $G$ and known as the adjacency spectrum of $G$, denoted by $\left(\eta_1 \leq \eta_2 \leq \eta_3 \leq... \leq \eta_n\right)$. The diagonal matrix of vertex degrees is defined as $\mathcal{D}(G) = diag \left[d_{\nu_{ij}}\right] \ \ \ for \ \ i = j$ where $d_{\nu_{ij}}$ denotes degree of certain vertex. Then Laplacian matrix ^[13] is ${L} (G) = \mathcal{D}(G)-\mathcal{A}(G)$ which can be elaborated as

Numerous implementation of Laplacian spectrum is involved in complex networks to solve theoretical problems, dynamical processes and topological structures explanation ^[14,15,16]. A large number of results related to Laplacian spectra has calculated in existing literature mentioned in ^{[17,18,19,20,21]}. For instance, the second smallest eigenvalue of Laplacian matrix is known as the diameter of a network. The Kirchhoff index of networks can be expressed by the sum of reciprocals of nonzero eigenvalues, and the number of spanning trees of networks can be determined by the product of all nonzero adjacency, Laplacian and signless Laplacian eigenvalues. Additionally, the synchronizability of a network can be determined by the the ratio of the maximum eigenvalue to the smallest nonzero one of its Laplacian matrix ^[22,23]. Consequently, calculating these spectra is of great interest though determining this analytically is a theoretical challenge. The signless Laplacian matrix, denoted by $£(G)$ and defined as

is a well-known parameter in algebraic graph theory to describe structure and topology of graphs and numerous results and applications about $£(G)$ are mentioned in ^{[24,25,26,27]}. Prism graph $\mathcal{R}^{m}_n$ is a famous family in graph theory generated by iterative method taking m-copies of cycle graph $C_n$ and then joining corresponding vertices as described in Figures 1 and 2. It is easy to evaluate that $\mathcal{R}^{m}_n$ contains $mn$ number of vertices and $(2m-1)n$ number of edges. Laplacian spectrum of $\mathcal{R}^{3}_n$ and $L(\mathcal{R}^{m}_n)$ are calculated in ^[2,28], respectively. Motivated by above work, we evaluated and analyzed the adjacency and signless Laplacian spectrum for generalized prism graph $\mathcal{R}^{m}_n$. Then the obtained results are utilized to examine some network related quantities. Some previous results used to evaluate required solutions in this paper are given below:

Definition 1.1. ^[29] Consider two matrices $X$ and $Y$ then Kronecker product $X \otimes Y$ is obtained by replacing $ij$-entry $x_{ij}$ of $X$ by $x_{ij}Y$. Some properties of kronecker product are mentioned in following lemmas.

Lemma 1.1. ^[30] Let $W \in M_{m, n}(F), X \in M_{p, q}(F), Y \in M_{n, k}(F), Z \in M_{q, r}(F)$ and $\alpha \in F$ then

● $(X \otimes Y)^{T} = X^{T} \otimes Y^{T}$;

● $(X \otimes Y)(X' \otimes Y') = X X' \otimes YY'$;

● $\alpha(X \otimes Y) = \alpha X \otimes Y = X \otimes \alpha Y$.

Consider the path and cycle graph with $n$ vertices, denoted by $P_n$ and $C_n$. Spectrum of $P_n$ and $C_n$ are calculated in existed literature.

Lemma 1.2. ^[31] The adjacency eigenvalues of cycle graph $C_n$ are $2cos\frac{2 \pi \mu}{n}$ where $\mu = 1, 2, ..., n-1$ and adjacency eigenvalues of path graph $P_m$ are $2cos\frac{ \pi \lambda}{n+1}$ where $\lambda = 1, 2, ..., m$.

Let the product of all non-zero eigenvalues of given matrix and sum of reciprocal of obtained eigenvalues are denoted by $\mathcal{A}^{m}_n$ and $\mathcal{B}^{m}_n$, respectively, that is

where ${\in_k}(k = 1, 2, ..., N)$ denotes eigenvalues of given adjacency matrix.

2.   Results

Some generalized results of prism network are evaluated in this section utilizing the edge parcel technique, degree checking strategy, vertex distance schemes, whole of degrees of neighbors technique, vertex adjacency schemes, vertex segment strategy, graph hypothetical devices, combinatorial techniques and expository strategies. In addition, Matlab and Maple are used for mathematical calculations and verification.

Theorem 2.1. Consider the adjacency matrix of generalized prism graph with m copies and vertices in each cycle, denoted by $\mathcal{A}(\mathcal{R}^{m}_n)$. Then, product of all eigenvalues is

and sum of reciprocal of nonzero eigenvalues is

Proof. The adjacency matrix of prism graph $\mathcal{R}^{m}_n$ is:

which can be written as

Thus by Lemma 1.1,

where matrix

is adjacency matrix of path graph with $m$ vertices say $P_m$. Then

Suppose, there exists two matrices $P, Q$ which are invertible and relate with $C_n$ and $P_m$ such that:

and

diagonal elements of these both upper triangular matrix is:

And clearly,

diagonal elements of this upper triangular matrix are defined as

Consequently, the adjacency eigenvalues for $n$-prism networks are

By utilizing the above results, one can get

and

Above theorem gives the exact results for adjacency matrix of generalized prism graph. Utilizing above theorem, we established following corollary for which is classic prism and closely related to results in ^[2].

Corollary 2.1. Product and sum reciprocal of eigenvalues for $\mathcal{R}^{m}_3$ are given as:

and

Product and reciprocal of sum of eigenvalues obtained from Laplacian matrix $\mathcal{L}$ of prism graph along with numerous application in complex networks is explained already in literature ^[28]. Now we calculate generalized formulae to obtain product and sum of eigenvalues of signless Laplacian matrix $£(G)$ of prism graph in following theorem.

Theorem 2.2. The product and sum of reciprocal nonzero eigenvalues of $£(P_m)$ are

Proof. The signless Laplacian matrix of prism graph $\mathcal{R}^{m}_n$ is:

which can be written as

Thus by Lemma 1.1

where matrix

is adjacency matrix of path graph with $m$ vertices say $P_m$. Then

where $I_n$ denotes the identity matrix of dimension $n \times n$. Actually, there exists invertible matrices $P, Q$ such that the matrices:

and

are both upper triangular with diagonal elements

And clearly,

is upper triangular matrix whose diagonal elements are

Consequently, the adjacency eigenvalues for $n$-prism networks are

By utilizing the above result, one can get

and

3.   Implementation of adjacency spectra

Spectral radius, graph energy, Kirchoff index, average path length, global mean first passage time and number of spanning trees are some network related quantities which can be calculated by utilizing above determined results in Theorems 2.1 and 2.2, and capable to enriches and extends the earlier results in literature.

3.1.   Kirchoff network descriptor

Novel concept of resistance distance was introduced by Randic and Klein ^[32] in which they considered one unit resistor as an edge and whole resistive network as graph $G$. In electrical network theory, effective resistance between nodes $\mu$ and $\lambda$ is called resistance distance, denoted by $r_{ \lambda \mu}$, can also be computed by ohm's law. Mathematically, the Kirchoff index is

Actually, $KI(G)$ is sum of resistance distances between all vertices pairs in $G$ with numerous applications in graph theory, physics and chemistry. Some recent publications related to Kirchoff index and its applications are cited in ^[33,34]. Consider a connected graph $G$ of order $M$ with $\epsilon _\lambda$ non-zero eigenvalues where $i = 1, 2, ..., N$. Then $KI(G)$ can be defined in terms of eigenvalues as ^[35]

Now we compute exact formula for $KI(\mathcal{R}^{m}_n)$ utilizing above result as follows:

By using the number of vertices of prism graph and results of Theorem 2.1, we evaluate:

Similarly, utilizing signless Laplacian matrix of prism graph $\mathcal{R}^{m}_n$, we obtain kirchoff index as:

3.2.   Global mean-first passage time

A network related important quantity mean-first passage time $({F}_{\lambda \mu})$ is utilized in estimation of transport speed for random walks in complex network systems whereas global mean-first passage time $(\mathcal{F}_{\lambda \mu})$ is used to measure diffusion efficiency which can be calculated by averaging the quantity $({F}_{\lambda \mu})$ over $\nu$ origins of particles and $(\nu-1)$ possible destinations ^[36,37].

The commuting time $T_{\lambda \mu}$ between vertices (nodes) $\lambda$ and $\mu$ is calculated as $2 \mathcal{E} r_{\lambda \mu}$ using previous results given in ^[14].

where $\mathcal{E}$ is size of graph G. Now, utilizing above Eqs (3.2) and (3.3), and discussions, global mean-first passage time for $\mathcal{R}^{m}_n$ is:

Since $\nu_m = nm$ and $\epsilon_m = (2m-1)$, therefore network size $\nu_m$ can be utilized to describe global mean-first passage time.

Similarly, utilizing signless Laplacian matrix of prism graph $\mathcal{R}^{m}_n$, we obtain global mean-first passage time such that

3.3.   Average path length

In computer sciences, interpretation of term "Small world" is very short average path length APL of mostly real world networks. Clustering coefficient, average path length and degree distribution are most robust and prominent measures of network topology. For a graph (or network) G, average number of steps along the shortest path $d_{\lambda\mu}$ is average path length (APL), denoted by $D_m$, which is a measure of the efficiency of mass transport or information on networks among all possible pairs of network nodes ^[14]. Then APL for $\mathcal{R}^{m}_n$ is defined as

If we consider an electrical network as complete graph then relation between the shortest paths $d_{\lambda \mu}(G)$ and effective resistance $r_{\lambda \mu}(G)$ given in reference ^[38]

where $|\, \nu \, |$ describes the order of complete graph $G$. We obtain following result from above Eqs (3.4) and (3.5),

By using the number of vertices of prism graph and results of Theorem 2.1, we evaluate:

Similarly, utilizing signless Laplacian matrix of prism graph $\mathcal{R}^{m}_n$, we obtain average path length such that

3.4.   The number of spanning trees

The standard random walks, reliability, resistor networks, transport, loop-erased random walks and self-organised criticality are well-known terms in complex networking and closely related to the number of spanning trees (NST) which proves the importance and numerous implementation of NST in various networks ^{[39,40,41,42,43]}. The Kirchhoff's Matrix-tree theorem ^[44,45] "Product of all nonzero eigenvalues of the Laplacian matrix of the graph results the number of spanning trees" can be utilized to calculate exact NST of prism graph $\mathcal{R}^{m}_n$ denoted by $\mathcal{N}_S (\mathcal{R}^{m}_n)$. Then

Similarly, utilizing signless Laplacian matrix of prism graph $\mathcal{R}^{m}_n$, we obtain the number of spanning trees such that

3.5.   Graph energies and spectral radius

Graph energies $E_\mathcal{G}$ and spectral radius $\mathcal{S_R}$ are network topology descriptor dependent upon eigenvalues of graph (network) matrices. Spectral radius has numerous contrivance in vibration theory, theoretical chemistry, combinatorial optimization, and communication networks, robustness analysis and electrical networks ^[5,6,7]. Graph energies are widely used in Huckle Molecular Orbital theory HMO, protein sequences and as a numerical invariant of chemical structures ^[46,47]. $E_\mathcal{G}$ and $\mathcal{S_R}$ are defined as sum of absolute eigenvalues and the maximum eigenvalue of adjacency matrices, respectively. Thus

Then by using above definitions, adjacency matrix of prism graph $\mathcal{R}^{m}_n$ and resuts obtained in Theorem 2.1, we have

Similarly, utilizing signless Laplacian matrix of prism graph $\mathcal{R}^{m}_n$, we obtain graph energies and spectral radius such that:

4.   Conclusions

In this article, we evaluated the exact formulae for adjacency and signless Laplacian spectrum of generalized prism graph utilizing algebraic methodologies. Then applied these evaluated explicit expressions to determine some network related quantities like global mean-first passage time, average path length, number of spanning trees, kirchoff network descriptor, graph energies and spectral radius which are potentially helpful to understand characterizations of different network's topology.

Acknowledgments

The authors extend their appreciation to the deputyship for Research & Innovation, Ministry of Education in Saudi Arabia for funding this research work through the project number (IFP-2020-72).

Conflict of interest

The authors declare no conflict of interest.