Computers, Materials & Continua DOI:10.32604/cmc.2022.031958
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, Γ(