Computers, Materials & Continua
DOI:10.32604/cmc.2022.031958
images

Article

The Kemeny’s Constant and Spanning Trees of Hexagonal Ring Network

Shahid Zaman1, Ali N. A. Koam2, Ali Al Khabyah2 and Ali Ahmad3,*

1Department of Mathematics, University of Sialkot, Sialkot, 51310, Pakistan
2Department of Mathematics, College of Science, Jazan University, New Campus, Saudi Arabia
3College of Computer Sciences and Information Technology, Jazan University, Jazan, Saudi Arabia
*Corresponding Author: Ali Ahmad. Email: ahmadsms@gmail.com
Received: 01 May 2022; Accepted: 16 June 2022

Abstract: Spanning tree (τ) has an enormous application in computer science and chemistry to determine the geometric and dynamics analysis of compact polymers. In the field of medicines, it is helpful to recognize the epidemiology of hepatitis C virus (HCV) infection. On the other hand, Kemeny’s constant (Ω) is a beneficial quantifier characterizing the universal average activities of a Markov chain. This network invariant infers the expressions of the expected number of time-steps required to trace a randomly selected terminus state since a fixed beginning state si. Levene and Loizou determined that the Kemeny’s constant can also be obtained through eigenvalues. Motivated by Levene and Loizou, we deduced the Kemeny’s constant and the number of spanning trees of hexagonal ring network by their normalized Laplacian eigenvalues and the coefficients of the characteristic polynomial. Based on the achieved results, entirely results are obtained for the Möbius hexagonal ring network.

Keywords: Matrix Analysis; hexagonal ring network; Kemeny’s constant; Spanning tree

1  Introduction

Obtaining the total number of spanning trees of any network is the central part of exploration in network theory, as spanning trees of any network grow exponentially through a network size. Earlier in the 1960s, researchers around the world explored numerous procedures of fluctuating efficiency methods. It uses various fields of computer science such as image processing, networking, and countless other usages of minimum spanning trees or entirely possible spanning trees of a network.

Another network invariant is entitled Kemeny’s constant (Ω). In [1], the Kemeny’s constant is proposed by Kemeny and spell. It is motivating to perceive that this unique network invariant is closely related to the analogous Spectrum of the normalized Laplacian (see Lemma 2.2 in the next section). Kemeny’s constant is formally defined as the expected number of steps desirable for the transition from a starting node to a terminus node. It is chosen randomly by a stationary distribution of unbiased random walks on network N. In finite ergodic Markov chains, the Ω has an essential property independent of the initial state of the Markov chain [2]. The adjacency matrix A(N) of N is a matrix whose (i,j)-entry is 1 if and only if ij∈EN and 0, otherwise. Define the Laplacian matrix of N as L(N)=D(N)−A(N), where D(N) is the diagonal matrix whose main diagonal entries are the degrees in N. In recent years, the method of using eigenvalues of normalized Laplacian, Γ(N), consisting of the matrix in spectral geometry and random walks [3,4], attracted the researchers due to its numerous applications.

1.1 Preliminaries

All the networks considered in this paper are finite, connected, simple, and undirected. Let N=(UN,EN) be any network, where UN denote the node-set and EN denote the link set. We represent the order of N as n=|UN| and its size as |EN|. The traditional notation and terminology not defined in this paper are referred to [2,3].

The adjacency matrix A(N) of N is a matrix whose (i,j)-entry is 1 if and only if ij∈EN and 0, otherwise. Define the Laplacian matrix of N as L(N)=D(N)−A(N), where D(N) is the diagonal matrix whose main diagonal entries are the degrees in N. We assume that μ1<μ2⩽⋯⩽μn be the eigenvalues of L(N). It is obvious that μ1=0 and μ2>0 if and only if N is a connected network. Further, regarding the results on L(N), we recommend the recent work [4] and the references within.

Let M be an m×n matrix. We assume that S⊂{1,2,…,m} and T⊂{1,2,…,n}. Denote M(S|T) for the submatrix of M, which is obtained by deleting the rows of S and the columns of T. Notably, we denote M(S|T) by M(i|j), where S={i} and T={j}.

In recent years, the method using eigenvalues of normalized Laplacian, Γ(𝑁), which consists of the matrix in spectral geometry and random walks [5,6], has attracted more and more researchers’ attention. Defining the normalized Laplacian of nonregular networks also attracted researchers. Furthermore, the normalized Laplacian of any network is defined as:

Γ(N)=I−D−12(N)A(N)D−12(N)=D−12(N)L(N)D−12(N).

Here, when a degree of the node wj in N is 0, then (dj)−12=0, see [5]. That is to say

(Γ(N))ij={1,if i=j;−1didj,if i≠j and vi is adjacent to vj;0,otherwise,

The notation (Γ(N))ij symbolizes the (i,j)-entry of Γ(N), and we assume that {λ1,λ2,…,λn} denote the Spectrum of the normalized Laplacian of N. These eigenvalues are labeled as 0=λ1<λ2⩽⋯⩽λn, with the fact that N is connected if and only if λ2>0. In [7], Chen and Zhang determined that the resistance distance can also be obtained from eigenvalues expressions and their multiplicities in the sense of normalized Laplacian.

The hexagonal system plays an essential role in theoretical chemistry. Since the hexagonal systems are natural network illustrations of benzenoid hydrocarbon [8]. Therefore, in various fields, hexagonal systems have been widely studied. The perfect matching in random hexagonal chain network is established by Kennedy et al. [9] in 1991. The hexagonal chain for Wiener index and Edge-Szeged index is determined in [10] and [11], respectively. In [12], Lou and Huang gave complete descriptions of the characteristic polynomial of a hexagonal system.

In this paper, motivated by [13–17] and from the normalized Laplacian decomposition theorem, we obtained the explicit closed-form formulations for Ω and τ for Δn as well as ∇n′.

1.2 Definition and Structures of the Two Hexagonal Ring Networks

We denote the linear hexagonal chain with n hexagons by Mn. The hexagonal ring network is denoted by Δn and computed from Mn by identifying the opposite boundary links in an ordered way. The Möbius hexagonal ring network ∇n′ obtained by Mn by identifying the opposite boundary links in a reversed way.

In this paper, we focus on two interesting molecular network types: the hexagonal ring network (see Fig. 1) and the Möbius hexagonal ring network (see Fig. 2). The hexagonal ring network Δn is the network obtained from the linear hexagonal chain Mn by identifying node 1 with (2n+1) the node 1′ with (2n+1)′, respectively. Similarly, the Möbius hexagonal ring network ∇n′ is the network obtained from the linear hexagonal chain Mn by identifying the node 1 with (2n+1)′, the node 1′ with (2n+1), respectively.

Figure 1: The hexagonal ring network

Figure 2: Möbius hexagonal ring network

2  Normalized Laplacian Polynomial Decomposition and Important Lemmas

In this section, we discuss some vital block matrices, characteristic polynomial, and the automorphisms of N, which will be used to prove our main results. We denote φ(B)=det(xI−B) for the characteristic polynomial of a matrix B, where B is a square matrix and I is the corresponding identity matrix. The automorphism of any network N is a permutation π of the nodes of N having the property that uv is a link in the network N, whenever π(u)π(v) is a link in N. We suppose that the network N is an automorphism in π. Therefore, we write it as a 1-cycle of disjoint product and its transpositions in the form π=(1¯)(2¯)⋯(m¯)(1,1′)(2,2′)⋯(k,k′). Thus, it is easy to compute that |UN|=m+2k, and assume that U0={1¯,2¯,…,m¯}, U1={1,2,…,k} and U2={1′,2′,…,k′}. After an appropriate organization of the nodes in N, the normalized Laplacian matrix Γ(N) can be arranged in the following way

Γ(N)=(ΓU00ΓU01ΓU02ΓU10ΓU11ΓU12ΓU20ΓU21ΓU22).

The submatrix ΓUij is formed by rows corresponding to nodes of the network N in Ui and columns corresponding to those in Uj, where i=0,1,2 and j=0,1,2. We assume that T=(Im00012Ik12Ik012Ik−12Ik)

is a block matrix in which the dimension of a block is the same as the corresponding blocks of Γ(N). Note that the automorphism of N is denoted by π. Hence ΓU11=ΓU22. Considering the unitary transformation TΓ(N)TT yields

TΓ(N)TT=(ΓR(N)00ΓS(N)).(1)

where ΓR(N)=(ΓU002ΓU012ΓU10ΓU11+ΓU12),ΓS(N)=ΓU11−ΓU12.

In [15], the first author of this article mentioned the decomposition theorem of the Laplacian polynomial. In the following lemma, it is easy to see that the decomposition theorem for normalized Laplacian polynomial is also existed as:

Lemma 2.1: The matrices Γ(N), ΓR(N) and ΓS(N) as defined above are, satisfies that φ(Γ(N))=φ(ΓR(N))φ(ΓS(N)).

The following two lemmas are essential to obtain our main results.

Lemma 2.2: [18] The Kemeny’s constant of a simple connected network N with n nodes is denoted by Ω and defined as Ω(N)=∑i=2n1λi.

Lemma 2.3: [5] The Spanning trees of a network N with order n and links m are denoted by τ(N) and defined as τ(N)=12m∏i=1ndi∏k=2nλk.

3  Important Matrices and the Spectrum of Γ(Δn)

According to Lemma 2.1, we firstly obtain the normalized Laplacian eigenvalues for Δn. Then we give the formula for the sum of the normalized Laplacian eigenvalues’ reciprocals and the product of the normalized Laplacian eigenvalues, which motivate us to calculate the Ω and the number of spanning trees of Δn. We also deduce the corresponding results based on our achieved results. Bearing in mind the labeled nodes of Δn as shown in Fig. 1, one can see that π=(1,1′)(2,2′)⋯(2n,(2n)′) is an automorphism of the network Δn. That is to say, U0=∅, U1={1,2,…,2n} and U2={1′,2′,…,(2n)′}. From the notation in (1), we may denote ΓR(Δn) and ΓS(Δn) as ΓR and ΓS respectively, and we have

ΓR=ΓU11+ΓU12,ΓS=ΓU11−ΓU12.

The matrices ΓU11 and ΓU12 are of order 2n×2n as given below:

ΓU11=(1−1600⋯0−16−161−160⋯000−161−16⋯0000−161⋯00⋮⋮⋮⋮⋱⋮⋮0000⋯1−16−16000⋯−161),

ΓU12=(−13000⋯000000⋯0000−130⋯000000⋯00⋮⋮⋮⋮⋱⋮⋮0000⋯−1300000⋯00).

Hence ΓR=(23−1600⋯0−16−161−160⋯000−1623−16⋯0000−161⋯00⋮⋮⋮⋮⋱⋮⋮0000⋯23−16−16000⋯−161)2n×2n

and ΓS=(43−1600⋯0−16−161−160⋯000−1643−16⋯0000−161⋯00⋮⋮⋮⋮⋱⋮⋮0000⋯43−16−16000⋯−161)2n×2n.

For the sake of simplicity, we denote eigenvalues of ΓR and ΓS are respectively, as η1⩽η2⩽⋯⩽η2n and ξ1⩽ξ2⩽⋯⩽ξ2n. Furthermore, the Spectrum of Γ(Δn) is exactly {η1,η2,…,η2n ,ξ1,ξ2,…,ξ2n}, due to Lemma 2.1. Obviously, η1=0, ηi>0 (i=2,…,2n) and ξj>0 (j=1,…,2n). It is easy to calculate that |UΔn|=|U∇n′|=4n and |EΔn|=|E∇n′|=5n.

Further on, we introduce a matrix named Q, where Q is a matrix constructed from ΓR with the (1,2n)-entry and the (2n,1)-entry by replacing 0. We consider the i-th order principal submatrix, Qi (resp. Ci), formed by the first i rows and corresponding columns (resp. the last i rows and corresponding columns) of Q. Put qi:= det Qi and ci:= det Ci. Put q0=1, c0=1 and it is straightforward that qi=ci for all even i.

Lemma 3.1: For 0⩽i⩽2n, qi=6−i2−1[3+6+(−1)i(3−6)](i+1).

Proof. Since it is easy to see that q1=23, q2=12, q3=29. For 3⩽i⩽2n, expanding detQi with respect to its last row yields

qi={qi−1−16qi−2,ifiiseven;23qi−1−16qi−2,ifiisodd.

Let di=q2i if 0⩽i⩽n, let ei=q2i+1 if 0⩽i⩽n−1. Furthermore, c0=1, d0=23 and for i⩾1, then one has

{di=ei−1−16di−1,ei=23di−16ei−1.(2)

From the first equation in (2), one has ei−1=di+16di−1. Hence, ei=di+1+16di. Substituting ei−1 and ei into the second equation in (2) yields di+1=13di−136di−1,i⩾1. Keeping the same procedure, one can obtain that ei+1=13ei−136ei−1,i⩾1, and qi satisfies the below recurrence relation

qi=13qi−2−136qi−4,q0=1,q1=23,q2=12,q3=29.(3)

Then, the characteristic equation of (3) is x4=13x2−136, the roots of which are x1=x2=16 and x3=x4=−16. The general solution of (3) is given by

qi=(16)i(y1+iy2)+(−16)i(y3+iy4).(4)

Together with the initial conditions of (4), the system of equations yields

{y1+y3=1,16(y1+y2)−16(y3+y4)=23,(16)2(y1+2y2)+(−16)2(y3+2y4)=12,(16)3(y1+3y2)+(−16)3(y3+3y4)=29.

The unique solution of this system can be found to be y1=3+66, y2=3+66, y3=3−66, y4=3−66. We get our desired result by substituting y1,y2,y3 and y4 in (4).

Considering the procedure as the proof of Lemma 3.1, it is easy to determine the following results.

Lemma 3.2: For 0⩽i⩽2n, ci=14⋅6−i2[2+6+(−1)i(2−6)](i+1).

Based on Lemmas 3.1 and 3.2, we determine a2n−1 and a2n−2. For the sake of simplicity, we denote the entries of ΓR by lij, i,j=1,2,…,2n.

Lemma 3.3: −a2n−1=10n26n.

Proof. Since the number −a2n−1 (=(−1)2n−1a2n−1) is the sum of all those principal minors of ΓR which have 2n−1 rows and columns (see [19, P5]); we have

−a2n−1=∑i=12ndetΓR(i|i)=q2n−1+c2n−1+∑i=22n−1detΓR(i|i).

For 2⩽i⩽2n−1, one has

ΓR(i|i)=(l11−16⋯00⋯0−16−16l22⋯00⋯00⋮⋮⋱⋮⋮⋱⋮⋮00⋯li−1,i−10⋯0000⋯0li+1,i+1⋯00⋮⋮⋱⋮⋮⋱⋮⋮00⋯00⋯l2n−1,2n−1−16−160⋯00⋯−16l2n,2n)(2n−1)×(2n−1).

Let X=(0Ii−1I2n−i0). It is evident that XTΓR(i|i)X={Q2n−1,iiseven;C2n−1,iisodd.

Thus we have detΓR(i|i)={q2n−1,iiseven;c2n−1,iisodd.

Therefore,

−a2n−1=q2n−1+c2n−1+∑i=22n−1detΓR(i|i)=nq2n−1+nc2n−1=n(4n6n+n6n−1)=10n26n.

This completes the proof of Lemma 3.3.

Lemma 3.4: a2n−2 =25n4−7n23⋅6n

Proof. Since the number a2n−2 (=(−1)2n−2a2n−2) is the sum of all those principal minors of ΓR which have 2n−2 rows and columns (see [19, P5]), one has

a2n−2=∑1⩽i<j⩽2ndetΓR({i,j}|{i,j}).

We proceed further by considering the below subcases.

Subcase 1: i=1,j∈{2,3,…,2n}. Let

Q=(l2,2⋯00⋮⋱⋮⋮0⋯lj−2,j−2−160⋯−16lj−1,j−1)

Together with the convention that detQ=1, whence j=2. Then

ΓR({1,j}|{1,j})=(Q00C2n−j).

Hence,

∑j=22ndetΓR({1,j}|{1,j})=∑j=22ndetQdetC2n−j=∑j=22ncj−2c2n−j=10n3−4n6n.

Subcase 2: j=2n,i∈{2,3,…,2n−1}. Let

Q′=(li+1,i+1⋯00⋮⋱⋮⋮0⋯l2n−2,2n−2−160⋯−16l2n−1,2n−1)

with the convention that detQ′=1 if i=2n−1. Then

ΓR({i,2n}|{i,2n})=(Qi−100Q′).

Hence,

∑i=22n−1detΓR({i,2n}|{i,2n})=∑i=22n−1detQi−1detQ′=∑i=22n−1qi−1q2n−1−i=2(10n3−19n+9)3⋅6n.

Subcase 3: For 1<i<j<2n, we have

ΓR({i,j}|{i,j})=(Qi−10Q10Q20Q1T0C2n−j),

where

Q1=(00⋯−1600⋯0⋮⋮⋱⋮00⋯0),Q2=(li+1,i+1−16⋯0−16li+2,i+2⋯0⋮⋮⋱⋮00⋯lj−1,j−1)

together with the convention that detQ2=1, whence j=i+1. Let Y=(0Ii−1000Ij−i−1I2n−j00), we can see that

YTΓR({i,j}|{i,j})Y=(C2n−jQ1T0Q1Qi−1000Q2).

Notice that for even j, (C2n−jQ1TQ1Qi−1)=Q2n−1−j+i and detQ2=qj−i−1 and thus

detΓR({i,j}|{i,j})=q2n−1−j+iqj−i−1.

Otherwise, it is evident that det(C2n−jQ1TQ1Qi−1)=c2n−1−j+i and detQ2=cj−i−1, and thus

detΓR({i,j}|{i,j})=c2n−1−j+icj−i−1.

Therefore,

∑1<i<j<2ndetΓR({i,j}|{i,j})=∑1<i<j<2n,jis evenq2n−1−j+iqj−i−1+∑1<i<j<2n,jis oddc2n−1−j+icj−i−1

=25n4−50n3−7n2+50n−183⋅6n.

Hence, a2n−2=∑1⩽i<j⩽2ndetΓR({i,j}|{i,j})=25n4−7n23⋅6n.

Thus, we complete proof of Lemma 3.4.

Hence, we introduce a matrix F, where F is a matrix obtained from ΓS with the (1,2n)-entry and the (2n,1)-entry by replacing 0. We give the detail for i-th order of principal submatrix, Fi (resp. Ui), obtain from the first i rows and corresponding columns (resp. the last i rows and corresponding columns) of F. Put fi:=detFi, ui:=detUi and fixed f0=1, u0=1. Through the below observations, we proceed further.

Observation 3.5: For 0⩽i⩽2n, fi=112⋅6i[((3+23)+(−1)i(3−23))((2+1)i+1−(2−1)i+1)].

Proof of Observation 3.5: It is routine to check that f1=43, f2=76, f3=43. For 3⩽i⩽2n, expanding detFi respect to its last row yields

fi={fi−1−16fi−2,ifiiseven;43fi−1−16fi−2,ifiisodd.

Let si=f2i, if 0⩽i⩽n and let ti=f2i+1, if 0⩽i⩽n−1. For i⩾1, we set that s0=1 and t0=43, then one has

{si=ti−1−16si−1,ti=43si−16ti−1.(5)

From the first equation of (5), we have ti−1=si+16si−1, replace i−1 by i, we have ti=si+1+16si.

Putting the values of ti−1 and ti into the second equation in (5) gives si+1=si−136si−1,i⩾1. By keeping the same procedure, we have ti+1=ti−136ti−1,i⩾1. Therefore, fi satisfies the below recurrence relation

fi=fi−2−136fi−4,f0=1,f1=43,f2=76,f3=43.(6)

Then in (6) the characteristic equation is x4=x2−136 and its roots are x1=1+26, x2=−1+26, x3=2−16 and x4=−2−16. The general solution of (6) is given by

fi=(1+26)iy1+(−1+26)iy2+(2−16)iy3+(−2−16)iy4.(7)

Together with the initial conditions in (6) gives the following system of equations

{y1+y2+y3+y4=1,1+26(y1−y2)+2−16(y3−y4)=43,(1+26)2(y1+y2)+(2−16)2(y3+y4)=76,(1+26)3(y1−y2)+(2−16)3(y3−y4)=43.

The unique solution of this system of equations is y1=(1+2)(3+23)12, y2=(1+2)(3−23)12, y3=(1−2)(3+23)12 and y4=(1−2)(3−23)12. By putting the values of y1,y2,y3 and y4 in (7), it is easy to get the desired result.

We give the below observation with the same procedure as in the proof of Observation 3.5.

Observation 3.6: For 0⩽i⩽2n, ui=18⋅6i[((2+3)+(−1)i(2−3))((2+1)i+1−(2−1)i+1)].

By using the expansion to determine detΓS with regards to its last row, one has

detΓS=detF2n−1+16[(−16)2n−1−16detU2n−2]+16[(−16)2n−1−16detF2n−2]

=f2n−1−16(f2n−2+u2n−2)−26n.

Together with Observations 3.5 and 3.6, we obtain the following observation.

Observation 3.7: detΓS=[(2+1)n−(2−1)n]26n.

Now, we are ready to determine h2n−1. For the sake of simplicity, we denote the entries of ΓS with kij, i,j=1,2,…,2n.

Observation 3.8: h2n−1=−72n[(2+1)2n−(2−1)2n]4⋅6n.

Proof of Observation 3.8: Since −h2n−1 (=(−1)2n−1h2n−1) is the sum of all those principal minors of ΓS which have 2n−1 rows and columns (see also in [19, P5]), one has −h2n−1=∑i=12ndetΓS(i|i). For 2⩽i⩽2n−1, one has

ΓS(i|i)=(k11−16⋯00⋯0−16−16k22⋯00⋯00⋮⋮⋱⋮⋮⋱⋮⋮00⋯ki−1,i−10⋯0000⋯0ki+1,i+1⋯00⋮⋮⋱⋮⋮⋱⋮⋮00⋯00⋯k2n−1,2n−1−16−160⋯00⋯−16k2n,2n)(2n−1)×(2n−1).

By the same procedure as in the detail of detΓR(i|i)(2⩽i⩽2n−1) in Lemma 3.3, we have

−h2n−1=f2n−1+u2n−1+∑i=22n−1detΓS(i|i)=nf2n−1+nu2n−1=72n[(2+1)2n−(2−1)2n]4⋅6n.

This completes the proof of Observation 3.8.

The below proposition is a direct consequence of Lemma 2.2.

Proposition 3.9: Let Δn be a zig-zag polyhex network with n hexagons. Then

Ke(N)=∑i=22n1ηi+∑j=12n1ξj.(8)

The eigenvalues of ΓR are characterized as 0=η1<η2⩽⋯⩽η2n and the eigenvalues of ΓS are 0<ξ1⩽ξ2⩽⋯⩽ξ2n.

In the following propositions, we derived the expressions ∑i=22n1ηi and ∑j=12n1ξj.Based on the relationship between roots and coefficients of φ(ΓR) and φ(ΓS)

Proposition 3.10: Let 0=η1<η2⩽⋯⩽η2n be eigenvalues of ΓR. Then

∑i=22n1ηi=25n2−730.

Proof. Let φ(ΓR)=x2n+a1x2n−1+⋯+a2n−2x2+a2n−1x=x(x2n−1+a1x2n−2+⋯+a2n−2x+a2n−1),

where a2n−1≠0. Then η2,η3,…,η2n are the roots of the following equation

x2n−1+a1x2n−2+⋯+a2n−2x+a2n−1=0.

That is to say, 1η2,1η3,…,1η2n are the roots of a2n−1x2n−1+a2n−2x2n−2+⋯+a1x+1=0.

From the Vieta’s Theorem, one has

∑i=22n1ηi=−a2n−2a2n−1.(9)

Putting Lemmas 3.3 and 3.4 into (9) yields ∑i=22n1ηi=25n2−730, as desired.

Proposition 3.11: Let ξ1,ξ2,…,ξ2n be eigenvalues of ΓS. Then

∑i=12n1ξi=72n4⋅(2+1)n−(2−1)n(2+1)n+(2−1)n.

Proof. Let φ(ΓS)=x2n+h1x2n−1+⋯+h2n−1x+h2n,

where h2n≠0. Then ξ1,ξ2,…,ξ2n are the roots of the following equation

x2n+h1x2n−1+⋯+h2n−1x+h2n=0.

That is to say, 1ξ1,1ξ2,…,1ξ2n are the roots of

h2nx2n+h2n−1x2n−1+⋯+h1x+1=0.

Bear in mind the Vieta’s Theorem; we have

∑i=12n1ξi=−h2n−1h2n=−h2n−1detΓS.(10)

To obtain the expression ∑i=12n1ξi, it is enough to obtain h2n−1 and detΓS in (10). In view of (10), Observations 3.7 and 3.8, Proposition 3.11 follows directly.

Now, we will calculate some significant invariants related to Δn (resp. ∇n′) by the expression of the eigenvalues of Γ(N). We also contribute closed-form formulae of Ω and τ for Δn (resp. ∇n′) in the subsequent section.

4  Main Results

4.1 The Kemeny’s Constant and the Number of Spanning Trees of Δn

Let Δn is a hexagonal ring network with n hexagons. Then

Theorem 4.1: Ω(Δn)=25n2−730+72n4⋅(2+1)n+(2−1)n(2+1)n−(2−1)n.

Proof. Based on Propositions 3.1–3.3 and |EΔn|=5n., we obtain the result immediately.

Theorem 4.2: τ(Δn)=n[(2+1)n−(2−1)n]2.

Proof. Based on the proof of Proposition 3.10, it is easy to see that η2,…,η2n are the roots of an equation x2n−1+a1x2n−2+⋯+a2n−2x+a2n−1=0. Thereby, one has ∏i=22n ηi=−a2n−1. By Lemma 3.3, we have

∏i=22n⁡ηi=10n26n.

Similarly,

∏j=12n⁡ξj=[(2+1)n−(2−1)n]26n.

Note that

∏v∈UΔndΔn(v)=22n32n,|EΔn|=5n.

Together with Lemma 2.3, we get our desired result.

4.2 The Kemeny’s Constant and the Number of Spanning Trees of ∇n′

Now, we devote our attention to determining the Ω and the τ for the Möbius hexagonal ring network ▽n′. Based on the labeled nodes of ∇n′ as shown in Fig. 2, one has π=(1,1′)(2,2′)⋯(2n,(2n)′) is an automorphism of ∇n′. From Fig. 2, we have U0=∅, U1={1,2,…,2n} and U2={1′,2′,…,(2n)′}. For the sake of simplicity, we denote ΓR(∇n′) and ΓS(∇n′) to ΓR′ and ΓS′, respectively. Thereby, it is easy to see that ΓR′=ΓR and

ΓS′=(43−1600⋯0016−161−160⋯0000−1643−16⋯00000−161⋯000⋮⋮⋮⋮⋱⋮⋮⋮0000⋯1−1600000⋯−1643−1616000⋯0−161)2n×2n.

Note that η1,η2,…,η2n are the spectrums of ΓR′ and suppose that βj′(1⩽i⩽2n) are the spectra of ΓS′. Due to Lemma 2.1, we have the normalized Laplacian eigenvalues of ∇n′ is {η1,…,η2n,β1′,…,β2n′}. In the following theorem, we give the formula for Ω and the τ for ∇n′.

Theorem 4.3: Ω(∇n′)=25n2−730+72n4⋅(2+1)n−(2−1)n(2+1)n+(2−1)n.

Proof. We denote h2n−1′ as the coefficient of x in det(xIn−ΓS′), and expand detΓS′ with regards to the last row, we have

detΓS′=w2n−1−16(w2n−2+u2n−2)+26n=[(2+1)n+(2−1)n]26n.

Similar to the method applied in Proposition 3.11, we have h2n−1′=h2n−1. Hence

Ω(∇n′)=∑i=22n1ηi+∑j=12n1βj′=25n2−730−h2n−1′detΓS′=25n2−730+72n4⋅(2+1)n−(2−1)n(2+1)n+(2−1)n⋅

Theorem 4.4: τ(∇n′)=n[(2+1)n+(2−1)n]2.

Proof. By keeping the same discussion as in the proof of Theorem 4.2, one has

∏i=22nηi=10n26n,∏j=12nβj′=[(2+1)n+(2−1)n]26n.

Note that

∏v∈U▽n′d∇n′(v)=22n32n,|E∇n′|=5n.

With the above expressions and Lemma 2.3, we get our desired result.

5  Comparison and Discussion

Theorem 4.1 and Theorem 4.2 implies that the Ω(Δn) and τ(Δn) of our considered network scales linearly and in direct proportion with n. We have verified our precise results in Figs. 3 and 4, which show that when we increase n, consequently Ω(Δn) and τ(Δn) also increases. Our findings give some new insights that can readily distinguish the structure of significant categories in our network. Similarly, Theorem 4.3 and Theorem 4.4 implies that the Ω(∇n′) and τ(∇n′) of our considered network scales linearly and in direct proportion with n. We have verified our precise results in Figs. 5 and 6, which show that when we increase n, consequently Ω(∇n′) and τ(∇n′) also increases.

Figure 3: Spanning trees and n in Ωn

Figure 4: Spanning trees and n in Δn

Figure 5: Kemeney’s constant and n in ∇n′

Figure 6: Spanning trees and n in ∇n′

Figs. 7 and 8 reflect the relationship between Ω(Δn), τ(Δn) and Ω(∇n′), τ(∇n′) respectively.

Figure 7: Comparison of Ω and τ in Δn

Figure 8: Comparison of Ω and τ in ∇n′

6  Concluding Remarks

In this paper, bear in mind the spectrums of normalized Laplacian; we identified the explicit closed-form formulae of Ω and τ for Δn and ∇n′, respectively. It is natural and exciting to study the hitting times of random walk for the hexagonal ring network and the Möbius hexagonal ring network. We will do it shortly.

Funding Statement: The authors received no specific funding for this study.

Conflicts of Interest: The authors declare they have no conflicts of interest to report regarding the present study.

References

 1.  J. G. Kemeny and J. L. Snell, Finite Markov Chains. New York, Berlin, Heidelberg, Tokyo: Springer-Verlag, 1960.

 2.  J. J. Hunter, “The role of Kemeny’s constant in properties of Markov chains,” Communications in Statistics-Theory and Methods, vol. 43, pp. 1309–1321, 2014.

 3.  S. Zaman and A. Ali, “On connected graphs having the maximum connective eccentricity index,” Journal of Applied Mathematics and Computing, vol. 67, no. 1, pp. 131–142, 2021.

 4.  S. Kirkland, “The group inverse of the Laplacian matrix of a graph, Combinatorial matrix theory,” in Adv. Courses Math., CRM Barcelona, Cham: Birkhäuser/Springer, pp. 131–171, 2018.

 5.  F. R. K. Chung, Spectral Graph Theory, RI: American Mathematical Society Providence, 1997.

 6.  L. Lovász, “Random walks on graphs: A survey, in combinatorics, Paul Erdös is Eighty,” Bolyai Society Mathematical Studies, vol. 2, no. 1, pp. 1–46, 1993.

 7.  L. H. Feng, I. Gutman and G. H. Yu, “Degree Kirchhoff index of unicyclic graphs,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 69, pp. 629–648, 2013.

 8.  I. Gutman and S. J. Cyvin, Introduction to the Theory of Benzenoid Hydrocarbon, Belin, Heidelberg: Springer-Verlag, 1989.

 9.  J. W. Kennedy and L. V. Quintas, “Perfect mathchings in random hexagonal chain graphs,” Journal of Mathematical Chemistry, vol. 6, no. 1, pp. 377–383, 1991.

10. A. A. Dobrymin, I. Gutman, S. Klavžar and P. Žigert, “Wiener index of hexagonal systems,” Acta Applicandae Mathematicae, vol. 72, no. 3, pp. 247–294, 2002.

11. S. Z. Wang and B. L. Liu, “A method of calcutaing the edge-szeged index of hexagonal chain,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 68, pp. 91–96, 2012.

12. Z. Z. Lou and Q. X. Huang, “On the characteristic polynomial of a hexagonal system and its application,” Journal of Mathematical Research with Applications, vol. 34, pp. 265–277, 2014.

13. D. Q. Li and Y. P. Hou, “The normalized Laplacian spectrum of quadrilateral graphs and its applications,” Applied Mathematics and Computation, vol. 297, no. 4, pp. 180–188, 2017.

14. Y. G. Pan and J. P. Li, “Kirchhoff index, multiplicative degree-Kirchhoff index and spanning trees of the linear crossed hexagonal chains,” International Journal of Quantum Chemistry, vol. 118, pp. e25787, 2018.

15. S. Zaman, “Spectral analysis of three invariants associated to random walks on rounded networks with 2n-pentagons,” International Journal of Computer Mathematics, vol. 99, no. 3, pp. 465–486, 2022.

16. S. Zaman, F. A. Abolaban, A. Ahmad and M. A. Asim, “Maximum H-index of bipartite network with some given parameters,” AIMS Mathematics, vol. 6, no. 5, pp. 5165–5175, 2021.

17. S. Zaman, “Cacti with maximal general sum-connectivity index,” Journal of Applied Mathematics and Computing, vol. 65, no. 1–2, pp. 147–160, 2021.

18. A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky and P. Tiwari, “The electrical resistance of a graph captures its commute and cover times,” Computational Complexity, vol. 6, no. 4, pp. 312–340, 1996.

19. R. B. Bapat, Graphs and Matrices, New York: Springer, 2010.

images
This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.