|Computers, Materials & Continua |
The Kemeny’s Constant and Spanning Trees of Hexagonal Ring Network
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: firstname.lastname@example.org
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 . 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
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 , 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 . In finite ergodic Markov chains, the has an essential property independent of the initial state of the Markov chain . The adjacency matrix of is a matrix whose -entry is if and only if and , otherwise. Define the Laplacian matrix of as where is the diagonal matrix whose main diagonal entries are the degrees in . In recent years, the method of using eigenvalues of normalized Laplacian, , consisting of the matrix in spectral geometry and random walks [3,4], attracted the researchers due to its numerous applications.
All the networks considered in this paper are finite, connected, simple, and undirected. Let be any network, where denote the node-set and denote the link set. We represent the order of as and its size as . The traditional notation and terminology not defined in this paper are referred to [2,3].
The adjacency matrix of is a matrix whose -entry is if and only if and , otherwise. Define the Laplacian matrix of as where is the diagonal matrix whose main diagonal entries are the degrees in . We assume that be the eigenvalues of . It is obvious that and if and only if is a connected network. Further, regarding the results on we recommend the recent work  and the references within.
Let be an matrix. We assume that and . Denote for the submatrix of which is obtained by deleting the rows of and the columns of . Notably, we denote by , where and .
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:
Here, when a degree of the node in is 0, then see . That is to say
The notation symbolizes the -entry of and we assume that denote the Spectrum of the normalized Laplacian of . These eigenvalues are labeled as with the fact that is connected if and only if . In , 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 . Therefore, in various fields, hexagonal systems have been widely studied. The perfect matching in random hexagonal chain network is established by Kennedy et al.  in 1991. The hexagonal chain for Wiener index and Edge-Szeged index is determined in  and , respectively. In , Lou and Huang gave complete descriptions of the characteristic polynomial of a hexagonal system.
We denote the linear hexagonal chain with hexagons by . The hexagonal ring network is denoted by and computed from by identifying the opposite boundary links in an ordered way. The Möbius hexagonal ring network obtained by 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 is the network obtained from the linear hexagonal chain by identifying node with the node with , respectively. Similarly, the Möbius hexagonal ring network is the network obtained from the linear hexagonal chain by identifying the node with , the node with , respectively.
In this section, we discuss some vital block matrices, characteristic polynomial, and the automorphisms of , which will be used to prove our main results. We denote for the characteristic polynomial of a matrix , where is a square matrix and is the corresponding identity matrix. The automorphism of any network is a permutation of the nodes of having the property that is a link in the network , whenever is a link in . We suppose that the network is an automorphism in . Therefore, we write it as a -cycle of disjoint product and its transpositions in the form Thus, it is easy to compute that and assume that and After an appropriate organization of the nodes in , the normalized Laplacian matrix can be arranged in the following way
The submatrix is formed by rows corresponding to nodes of the network in and columns corresponding to those in , where and We assume that
is a block matrix in which the dimension of a block is the same as the corresponding blocks of Note that the automorphism of is denoted by . Hence Considering the unitary transformation yields
In , 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 , and as defined above are, satisfies that
The following two lemmas are essential to obtain our main results.
Lemma 2.2:  The Kemeny’s constant of a simple connected network with nodes is denoted by and defined as
Lemma 2.3:  The Spanning trees of a network with order and links are denoted by and defined as .
According to Lemma 2.1, we firstly obtain the normalized Laplacian eigenvalues for . 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 . We also deduce the corresponding results based on our achieved results. Bearing in mind the labeled nodes of as shown in Fig. 1, one can see that is an automorphism of the network . That is to say, , and From the notation in (1), we may denote and as and respectively, and we have
The matrices and are of order as given below:
For the sake of simplicity, we denote eigenvalues of and are respectively, as and . Furthermore, the Spectrum of is exactly , due to Lemma 2.1. Obviously, , and . It is easy to calculate that and
Further on, we introduce a matrix named , where is a matrix constructed from with the -entry and the -entry by replacing . We consider the -th order principal submatrix, (resp. ), formed by the first rows and corresponding columns (resp. the last rows and corresponding columns) of . Put det and det Put , and it is straightforward that for all even .
Lemma 3.1: For ,
Proof. Since it is easy to see that , . For expanding with respect to its last row yields
Let if , let if . Furthermore, and for then one has
Together with the initial conditions of (4), the system of equations yields
The unique solution of this system can be found to be , , , . We get our desired result by substituting and in (4).
Considering the procedure as the proof of Lemma 3.1, it is easy to determine the following results.
Lemma 3.2: For ,
Based on Lemmas 3.1 and 3.2, we determine and . For the sake of simplicity, we denote the entries of by , .
Lemma 3.3: .
Proof. Since the number is the sum of all those principal minors of which have rows and columns (see [19, P5]); we have
For , one has
Let It is evident that
Thus we have
This completes the proof of Lemma 3.3.
Proof. Since the number is the sum of all those principal minors of which have rows and columns (see [19, P5]), one has
We proceed further by considering the below subcases.
Subcase 1: . Let
Together with the convention that , whence . Then
Subcase 2: . Let
with the convention that if . Then
Subcase 3: For , we have
together with the convention that , whence . Let we can see that
Notice that for even , and and thus
Otherwise, it is evident that and , and thus
Thus, we complete proof of Lemma 3.4.
Hence, we introduce a matrix , where is a matrix obtained from with the -entry and the -entry by replacing . We give the detail for -th order of principal submatrix, (resp. ), obtain from the first rows and corresponding columns (resp. the last rows and corresponding columns) of . Put , and fixed , . Through the below observations, we proceed further.
Observation 3.5: For , .
Proof of Observation 3.5: It is routine to check that , , . For , expanding respect to its last row yields
Let , if and let , if . For we set that and , then one has
From the first equation of (5), we have replace by , we have
Putting the values of and into the second equation in (5) gives . By keeping the same procedure, we have Therefore, satisfies the below recurrence relation
Together with the initial conditions in (6) gives the following system of equations
We give the below observation with the same procedure as in the proof of Observation 3.5.
Observation 3.6: For ,
By using the expansion to determine with regards to its last row, one has
Together with Observations 3.5 and 3.6, we obtain the following observation.
Now, we are ready to determine . For the sake of simplicity, we denote the entries of with ,
Proof of Observation 3.8: Since is the sum of all those principal minors of which have rows and columns (see also in [19, P5]), one has For , one has
By the same procedure as in the detail of in Lemma 3.3, we have
This completes the proof of Observation 3.8.
The below proposition is a direct consequence of Lemma 2.2.
Proposition 3.9: Let be a zig-zag polyhex network with hexagons. Then
The eigenvalues of are characterized as and the eigenvalues of are .
In the following propositions, we derived the expressions and Based on the relationship between roots and coefficients of and
Proposition 3.10: Let be eigenvalues of . Then
where Then are the roots of the following equation
That is to say, are the roots of
From the Vieta’s Theorem, one has
Proposition 3.11: Let be eigenvalues of . Then
where . Then are the roots of the following equation
That is to say, are the roots of
Bear in mind the Vieta’s Theorem; we have
Now, we will calculate some significant invariants related to (resp. ) by the expression of the eigenvalues of . We also contribute closed-form formulae of and for (resp. ) in the subsequent section.
Let is a hexagonal ring network with hexagons. Then
Proof. Based on Propositions 3.1–3.3 and , we obtain the result immediately.
Proof. Based on the proof of Proposition 3.10, it is easy to see that are the roots of an equation . Thereby, one has By Lemma 3.3, we have
Together with Lemma 2.3, we get our desired result.
Now, we devote our attention to determining the and the for the Möbius hexagonal ring network Based on the labeled nodes of as shown in Fig. 2, one has is an automorphism of . From Fig. 2, we have , and For the sake of simplicity, we denote and to and , respectively. Thereby, it is easy to see that and
Note that are the spectrums of and suppose that are the spectra of . Due to Lemma 2.1, we have the normalized Laplacian eigenvalues of is . In the following theorem, we give the formula for and the for .
Proof. We denote as the coefficient of in , and expand with regards to the last row, we have
Similar to the method applied in Proposition 3.11, we have . Hence
Proof. By keeping the same discussion as in the proof of Theorem 4.2, one has
With the above expressions and Lemma 2.3, we get our desired result.
Theorem 4.1 and Theorem 4.2 implies that the and of our considered network scales linearly and in direct proportion with . We have verified our precise results in Figs. 3 and 4, which show that when we increase , consequently and 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 and of our considered network scales linearly and in direct proportion with . We have verified our precise results in Figs. 5 and 6, which show that when we increase , consequently and also increases.
In this paper, bear in mind the spectrums of normalized Laplacian; we identified the explicit closed-form formulae of and for and , 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.
|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.|