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

Article |

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: ahmadsms@gmail.com

Received: 01 May 2022; Accepted: 16 June 2022

Abstract: Spanning tree (

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 [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

All the networks considered in this paper are finite, connected, simple, and undirected. Let

The adjacency matrix

Let

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

The notation

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

1.2 Definition and Structures of the Two Hexagonal Ring Networks

We denote the linear hexagonal chain with

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

2 Normalized Laplacian Polynomial Decomposition and Important Lemmas

In this section, we discuss some vital block matrices, characteristic polynomial, and the automorphisms of

The submatrix

is a block matrix in which the dimension of a block is the same as the corresponding blocks of

where

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

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

Lemma 2.2: [18] The Kemeny’s constant of a simple connected network

Lemma 2.3: [5] The Spanning trees of a network

3 Important Matrices and the Spectrum of

According to Lemma 2.1, we firstly obtain the normalized Laplacian eigenvalues for

The matrices

Hence

and

For the sake of simplicity, we denote eigenvalues of

Further on, we introduce a matrix named

Lemma 3.1: For

Proof. Since it is easy to see that

Let

From the first equation in (2), one has

Then, the characteristic equation of (3) is

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

The unique solution of this system can be found to be

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

Lemma 3.3:

Proof. Since the number

For

Let

Thus we have

Therefore,

This completes the proof of Lemma 3.3.

Lemma 3.4:

Proof. Since the number

We proceed further by considering the below subcases.

Subcase 1:

Together with the convention that

Hence,

Subcase 2:

with the convention that

Hence,

Subcase 3: For

where

together with the convention that

Notice that for even

Otherwise, it is evident that

Therefore,

Hence,

Thus, we complete proof of Lemma 3.4.

Hence, we introduce a matrix

Observation 3.5: For

Proof of Observation 3.5: It is routine to check that

Let

From the first equation of (5), we have

Putting the values of

Then in (6) the characteristic equation is

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

The unique solution of this system of equations is

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

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

Observation 3.7:

Now, we are ready to determine

Observation 3.8:

Proof of Observation 3.8: Since

By the same procedure as in the detail of

This completes the proof of Observation 3.8.

The below proposition is a direct consequence of Lemma 2.2.

Proposition 3.9: Let

The eigenvalues of

In the following propositions, we derived the expressions

Proposition 3.10: Let

Proof. Let

where

That is to say,

From the Vieta’s Theorem, one has

Putting Lemmas 3.3 and 3.4 into (9) yields

Proposition 3.11: Let

Proof. Let

where

That is to say,

Bear in mind the Vieta’s Theorem; we have

To obtain the expression

Now, we will calculate some significant invariants related to

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

Let

Theorem 4.1:

Proof. Based on Propositions 3.1–3.3 and

Theorem 4.2:

Proof. Based on the proof of Proposition 3.10, it is easy to see that

Similarly,

Note that

Together with Lemma 2.3, we get our desired result.

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

Now, we devote our attention to determining the

Note that

Theorem 4.3:

Proof. We denote

Similar to the method applied in Proposition 3.11, we have

Theorem 4.4:

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

Note that

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

Theorem 4.1 and Theorem 4.2 implies that the

Figs. 7 and 8 reflect the relationship between

In this paper, bear in mind the spectrums of normalized Laplacian; we identified the explicit closed-form formulae of

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.

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. |