José Luis Palacios, Arianna Santamaría
Electrical and Computer Engineering Department, The University of New Mexico, Albuquerque, NM, USA.
DOI: 10.4236/ojapps.2025.158164   PDF    HTML   XML   58 Downloads   478 Views   Citations

Abstract

The hitting time index of a simple connected undirected graph $G$ is a recently defined topological descriptor, $HT\left(G\right)$ , which is computed using the expected hitting times of the random walk on $G$ . In this article, we find a new upper bound for $HT\left(G\right)$ , given in terms of the Kirchhoff index, and a new degree-weighted Kirchhoff index. Then we look at $HT\left(G\right)$ when $G$ is edge transitive, both in the regular and non-regular cases. We find closed-form formulas for some families of Cayley graphs, the complete bipartite graphs $K_{m,n}$ , and some subdivision graphs.

Keywords

Edge-Transitive Graphs, Cayley Graphs, Kirchhoff Index

Share and Cite:

1. Introduction

Throughout this article, a graph $G=\left(V,E\right)$ shall be taken as a finite simple connected undirected graph with vertex set $V=\left\{1,2,\cdots ,n\right\}$ , edge set $E$ , and vertex degrees $d_1,d_2,\cdots ,d_n$ . The reader may consult reference [1] for all pertinent graph theoretical details.

Mathematical Chemistry makes use of these graphs in order to model molecules by identifying the vertices as the atoms and the edges as the atomic bonds between the vertices. A plethora of descriptors, or topological indices, i.e., real-valued functions defined on the domain of all graphs, have been used in trying to capture the physico-chemical properties of the molecules and to classify them according to the values of their indices.

Several of these descriptors are defined in terms of electrical or probabilistic concepts, and these two areas are intimately related as we will point out below. A notable such descriptor is the Kirchhoff index defined in [2] as

$K\left(G\right)={\displaystyle \sum }_{i<j}{R}_{ij},$ (1)

where $R_{ij}$ is the effective resistance across vertices $i$ and $j$ when the graph is considered as an electrical network, and all the edges are endowed with a resistance of 1 ohm. This descriptor was a natural evolution of an earlier one, the Wiener index, introduced in [3] as

$W\left(G\right)={\displaystyle \sum }_{i<j}d\left(i,j\right),$ (2)

where $d\left(i,j\right)$ is the distance in the graph $G$ between vertices $i$ and $j$ . It is clear that for a tree $T$ one has $W\left(T\right)=K\left(T\right)$ and for a general $G$ , $W\left(G\right)\ge K\left(G\right)$ .

The simple random walk on $G$ is the Markov chain $\left\{X_n,n\ge 0\right\}$ with state space $V$ and uniform transition probabilities, that is, the walk jumps from vertex $i$ to any of its $d_i$ neighboring vertices with probability $\frac{1}{d_i}$ . The hitting time $T_j$ of the vertex $j$ is the random variable that counts the number of jumps needed by the random walk to reach the vertex $j$ for the first time:

$T_j=\text{inf}\left\{n\ge 0:X_n=j\right\},$

and its expected value, when the process is started in state $i$ is denoted by $E_i{T}_j$ . Notice that the definition implies $E_i{T}_i=0$ , and this should not be confused with the mean return time to $i$ , $E_i{T}_i^{+}=\frac{2\left|E\right|}{d_i}$ , defined for the random variable $T_i^{+}=\text{inf}\left\{n\ge 1:X_n=i\right\}$ . Reference [4] contains the basic facts about hitting times of Markov chains.

In [5], we showed that there is a close relationship between the Kirchhoff index of a graph $G$ and the expected hitting times for the random walk on $G$ , specifically

$K\left(G\right)=\frac{1}{2\left|E\right|}{\displaystyle \sum }_{i<j}\left(E_i{T}_j+E_j{T}_i\right),$ (3)

thus providing probabilistic ideas for the analysis of this index. Reference [6] gives a good introduction to the interplay between electric networks and random walks on graphs. One important result in this regard is the formula for the commute time between two vertices $i$ and $j$ , found in [7] and stating

$E_i{T}_j+E_j{T}_i=2\left|E\right|R_{ij},$ (4)

which can be simplified, in case there is some symmetry that guarantees both hitting times are equal, to

$E_i{T}_j=\left|E\right|R_{ij}.$ (5)

We will be using these results below.

A recent probabilistic/electrical index was proposed by Camby et al. in [8], the random walk index, defined as follows: across any two vertices $i$ and $j$ , a battery is placed between them so that a 1 ampere current enters $i$ and exits $j$ . This setup implies a voltage $v_x^{ij}$ on all vertices $x\in V$ , and a potential drop on any edge $\left(x,y\right)$ given by $v_x^{ij}-v_y^{ij}$ . If one inverts the polarity of the battery, then the potential difference on the edge $\left(x,y\right)$ is $v_y^{ij}-v_x^{ij}$ , and therefore, to avoid the dependance on the polarity of the battery, the authors consider the absolute value $\left|v_x^{ij}-v_y^{ij}\right|$ , and the summation of these values over all edges of the graph, i.e.:

${\widehat{d}}_{ij}={\displaystyle \sum }_{\left(x,y\right)\in E}\left|v_x^{ij}-v_y^{ij}\right|.$

The function $\widehat{d}$ defined on the pairs of vertices $ij$ by the value ${\widehat{d}}_{ij}$ is shown to be a metric on the set of vertices, and the random walk index is defined as

$RW\left(G\right)={\displaystyle \sum }_{i<j}{\widehat{d}}_{ij}.$(6)

Partly inspired by the ideas in [8], we defined in [9] a new probabilistic index, the hitting time index $HT\left(G\right)$ of a graph $G$ , as

$HT\left(G\right)={\displaystyle \sum }_{i<j}D\left(i,j\right),$ (7)

where $D\left(i,j\right)=\text{max}\left\{E_i{T}_j,E_j{T}_i\right\}$ .

We showed that $D\left(i,j\right)$ is actually a distance on the set of all vertices of $G$ , found some inequalities involving $HT\left(G\right)$ , $KG)$ , $W\left(G\right)$ , and $RW\left(G\right)$ , and computed $HT\left(G\right)$ for some families of graphs. These results were extended in [10], where we found tighter inequalities and closed-form expressions of $HT\left(G\right)$ for more families of graphs. The hitting time index is a good discriminator, in the sense that different graphs will get different values of $HT\left(G\right)$ , unlike the random walk index, which gives the same values to cycle graphs and linear graphs, for example, as mentioned in [9]. Moreover, recently there has been some interest in finding graphs that preserve the value of their Kirchhoff index after the removal of a vertex (see [11]). For example, for the 5-cycle, a removal of a vertex yields a 4-path, and the value of the Kirchhoff index of both graphs is 10. This may be interpreted as a discriminating weakness, to be contrasted with the $HT$ index, which gives a value of 50 to the first graph and a value of 38 to the second one. This issue deserves further research.

A simple way to compute $HT\left(G\right)$ starts by finding the transition probability $P$ of the random walk on $G$ , with entries $P\left(i,j\right)=\frac{1}{d_i}$ in case $i$ and $j$ are neighbors, and zero otherwise. We also use the matrix $W$ , all of whose rows are identical to the stationary distribution $\pi =\frac{1}{2\left|E\right|}\left[d_1,d_2,\cdots ,d_n\right]$ . Then we find the so-called fundamental matrix

$Z={\left(I-P+W\right)}^{-1},$

where $I$ is the $n\times n$ identity matrix. Now, the matrix $E$ of expected hitting times is found via the matrix $Z$ . Its entries are

$E\left(i,j\right)=E_i{T}_j=\left(Z\left(j,j\right)-Z\left(i,j\right)\right)/{\pi }_j.$

See [4] for a discussion of the matrices $Z$ and $E$ . Finally, the $HT$ index of the graph under consideration is found by adding $\left(\begin{array}{c}n-1\\ 2\end{array}\right)$ terms,

${\displaystyle \sum }_{i<j}\max \left\{E\left(i,j\right),E\left(j,i\right)\right\}.$

In this article, we continue with the study of $HT\left(G\right)$ . Specifically, we prove the inequality

$HT\left(G\right)\le 2\left|E\right|K\left(G\right)-K_{\min }\left(G\right),$

where $K_{\min }\left(G\right)$ is a new Kirchhoffian index defined by

$K_{\min }\left(G\right)={\displaystyle \sum }_{i<j}{R}_{ij}\min \left\{d_i,d_j\right\},$

which resembles indices such as the multiplicative and the additive degree-Kirchhoff indices, introduced in [12] and [13], respectively.

We also find closed-form formulas for the values of the $HT$ index in some families of graphs which are edge-transitive. For this concept of symmetry in graphs, we need first the definition of a graph automorphism, which is a bijection of the set of vertices of the graph that preserves adjacencies. Then we define a graph to be edge-transitive if for every pair of edges there is an automorphism that maps one edge onto the other. Thus, for example, the n-star graph is edge-transitive since every edge can be mapped into any other through a suitable rotation. The reader should be aware of the more restrictive definition of arc-transitivity where the automorphism maps any edge in any of its two orientations into any other edge. It is clear that arc-transitive graphs are edge-transitive, while the opposite is not true, as the n-star graph shows: in this graph, every edge can be mapped in one direction, but not in both onto any other. Examples of arc-transitive graphs are the n-cycle graph and the three-dimensional cube, where any edge, in any of its two orientations, can be mapped onto any other edge through rotations and symmetries.

2. A New Upper Bound

We showed in [9] that

$HT\left(G\right)\le 2\left|E\right|K\left(G\right).$ (8)

This inequality was improved in [10] as follows:

$HT\left(G\right)\le 2\left|E\right|K\left(G\right)-W\left(G\right),$ (9)

where the equality is attained in case $G=P_2$ .

We also showed that for any tree $T$ we have

$HT\left(T\right)\le 2\left|E\right|K\left(T\right)-W_2\left(T\right),$ (10)

where $W_2\left(G\right)={\displaystyle {\sum }_{i<j}d{\left(i,j\right)}^2}$ is the generalized Wiener index with parameter 2. The equality is attained for $P_2$ and $P_3$ .

We will prove a new inequality, which is better than (8) and non-comparable to (9), based on the following fact whose proof can be found in [14]:

Lemma 1. For a simple random walk on a graph $G$ and any $a,b\in G$ we have

$E_i{T}_j\le R_{ij}\left(2\left|E\right|-d_j\right).$ (11)

Now we prove the new upper bound in the following.

Proposition 1. For all $G$ we have

$HT\left(G\right)\le 2\left|E\right|K\left(G\right)-K_{\min }\left(G\right),$ (12)

where the equality is attained in case $G=P_2$ .

Proof. For all $i,j\in G$ we have

$\begin{array}{c}D\left(i,j\right)=\text{max}\left\{E_i{T}_j,E_j{T}_i\right\}\le \text{max}\left\{R_{ij}\left(2\left|E\right|-d_j\right),R_{ji}\left(2\left|E\right|-d_i\right)\right\}\\ =R_{ij}\left(2\left|E\right|-\text{min}\left\{d_i,d_j\right\}\right).\end{array}$

And thus

$\begin{array}{c}HT\left(G\right)={\displaystyle \sum }_{i<j}D\left(i,j\right)\le {\displaystyle \sum }_{i<j}{R}_{ij}\left(2\left|E\right|-\min \left\{d_i,d_j\right\}\right)\\ =2\left|E\right|K\left(G\right)-{\displaystyle \sum }_{i<j}{R}_{ij}\min \left\{d_i,d_j\right\}=2\left|E\right|K\left(G\right)-K_{\min }\left(G\right).\end{array}$ $•$

Obviously, our new (12) is always better than (21). It is also better than (9) in case

$W\left(G\right)<K_{\min }\left(G\right).$

This happens, for example, in the case of the complete graph $K_n$ , where $W\left(K_n\right)=\left(\begin{array}{c}n\\ 2\end{array}\right)<K_{\min }\left(K_n\right)={\left(n-1\right)}^2$ , for $n>2$ . Also, for the n-cycle, for any two vertices $i,j$ such that $d\left(i,j\right)=k$ , the corresponding term $R_{ij}\min \left\{d_i,d_j\right\}$ in $K_{\min }\left(G\right)$ has a value $2\frac{k\left(n-k\right)}{n}\ge k$ because $k\le \frac{n}{2}$ , and the inequality is strict for $k<\frac{n}{2}$ . Also, for any tree $T$

$W\left(T\right)=K\left(T\right)\le K_{\min }\left(T\right),$

and the inequality is strict if there is at least a pair $i,j\in T$ such that neither $i$ nor $j$ are leaves, i.e., the inequality is strict for all trees other than the n-star graph, $n\ge 2$ .

On the other hand, it is easy to produce examples of graphs $G$ where $K_{\min }\left(G\right)<W\left(G\right)$ : take $G_n$ to be the n-star graph with an additional edge connecting any two leaves (in other words, $G_n$ is a triangle with $n-3$ pendant vertices attached to the same vertex of the triangle). Then all summands in the computations of $W\left(G_n\right)$ and $K_{\min }\left(G_n\right)$ are the same except for the vertices in the triangle, which contribute a total of 3 for $W\left(G_n\right)$ and a total of 4 for $K_{\min }\left(G_n\right)$ , and the $2\left(n-3\right)$ pairs of vertices $i,j$ , where $i$ is either of the vertices with degree 2 of the triangle and $j$ is any pendant vertex. Each of these pairs contributes a distance 2 for $W\left(G_n\right)$ , but only an effective resistance $\frac{2}{3}+1$ for $K_{\min }\left(G_n\right)$ . Therefore, $4+2\left(\frac{2}{3}+1\right)\left(n-3\right)<3+4\left(n-3\right)$ and thus $K_{\min }\left(G_n\right)<W\left(G_n\right)$ .

This discussion shows then that the bounds (9) and (12) are noncomparable.

Another observation: (12) is better than (9) for all trees other than the n-star graph, $n\ge 2$ , but it seems to be worse than (10) for any tree other than the 2-star, though this conjecture needs a formal proof.

3. Edge-Transitive Graphs

As discussed in [15], an edge-transitive graph is either regular, or it is bipartite, where the partition consists of the set $V_1$ of all those vertices with the larger degree $M$ , and the set $V_2$ of those vertices with the smaller degree $m$ . The regular case is perhaps of lesser interest because for such case, the $HT$ index is equal to the Kirchhoff index multiplied by the number of edges of the graph, and potentially we could find $HT\left(G\right)$ through the value $K\left(G\right)$ , which has been studied extensively. Still, we discuss this case first.

As was shown in [15], for a regular edge-transitive graph we have

Lemma 2.

$E_a{T}_b=n-1,$ (13)

whenever $\left(a,b\right)\in E$ . Also,

$E_a{T}_b=E_b{T}_a,$ (14)

whenever $d\left(a,b\right)$ is even, where $d\left(a,b\right)$ is the distance in the graph between vertices $a$ and $b$ .

Immediate implications of (13) and (14) are collected in the following.

Corollary 1. For regular edge-transitive graphs we have

$D\left(a,b\right)=n-1,$ (15)

whenever $\left(a,b\right)\in E$ .

$D\left(a,b\right)=\left|E\right|R_{ab},$ (16)

whenever $d\left(a,b\right)$ is even.

Corollary 1 gives a substantial amount of information on how to compute the $HT$ index, but not all that is needed. For $d\left(a,b\right)>2$ , it is not clear how to get $E_a{T}_b$ if $d\left(a,b\right)$ is odd, and even when $d\left(a,b\right)$ is even, it is not evident what the value of $R_{ab}$ may be. Let $diam\left(G\right)=\text{max}\left\{d\left(a,b\right):a,b\in V\right\}$ . A first simple case where we can identify hitting times $E_a{T}_b$ other than the case when $d\left(a,b\right)=1$ is given in the following

Proposition 2. If $diam\left(G\right)=2$ then $E_a{T}_b=n$ , whenever $d\left(a,b\right)=2$ and therefore

$HT\left(G\right)=\frac{n}{2}\left(n^2-n-d\right).$

Proof. By conditioning on the first jump of the walk, it is clear that when $d\left(a,b\right)=2$ we have $E_a{T}_b=1+E_c{T}_b$ , where $c$ and $b$ are neighbors. But we know by the previous lemma that $E_c{T}_b=n-1$ , so $E_a{T}_b=n$ . Now, counting the pairs of vertices at distances 1 and 2, we have

$HT\left(G\right)=\frac{nd}{2}\left(n-1\right)+\left[\left(\begin{array}{c}n\\ 2\end{array}\right)-\frac{nd}{2}\right]n=\frac{n}{2}\left(n^2-n-d\right)$ (17)

□

Examples of graphs included in the previous proposition are the complete bipartite graphs $K_{n,n}$ and the Cayley unitary graphs $Cay\left(Z_{p^k},U_{p^k}\right)$ , for $p$ prime (see [15] for details on the latter). A more involved example, not covered in proposition 1, is the unitary Cayley graph $Cay\left(Z_{2p},U_{2p}\right)$ , for $p$ prime, that has diameter 3, and their hitting times depend only on the distances 1, 2 or 3 between their vertices, with values

$E{T}_1=2p-1,E{T}_2=\frac{2{\left(p-1\right)}^2}{p-2},E{T}_3=\frac{p\left(2p-3\right)}{p-2}.$ (18)

Now we simply count pairs of vertices at distances 1, 2, 3. For distance 1 we have $\frac{\left|V\right|d}{2}$ such pairs, where $d$ is the common degree, resulting in $p^2-p$ pairs. For distance 3, we use theorem 3.3 in [15], and notice that the vertex 0 only has the vertex $p$ at distance 3, and since this happens for all vertices, the total number of pairs at distance 3 is $p$ . A simple subtraction yields that the number of pairs of vertices at distance 2 is $p^2-p$ . Putting these facts and (18) together yields the following.

Proposition 3. For any prime $p$ we have

$HT\left(Cay\left(Z_{2p},U_{2p}\right)\right)=\left(p^2-p\right)\left(2p-1\right)+\left(p^2-p\right)\frac{2{\left(p-1\right)}^2}{p-2}+\frac{p^2\left(2p-3\right)}{\left(p-2\right)}.$

As a corollary, since for $Cay\left(Z_{2p},U_{2p}\right)$ we have $\left|E\right|=p\left(p-1\right)$ , we can also give a closed-form formula for the Kirchhoff index of these graphs:

Corollary 2. For any prime $p$ we have

$K\left(Cay\left(Z_{2p},U_{2p}\right)\right)=\left(2p-1\right)+\frac{2{\left(p-1\right)}^2}{p-2}+\frac{p\left(2p-3\right)}{\left(p-2\right)\left(p-1\right)}.$

The Kirchhoff index of Cayley graphs has been studied in some depth, usually through the calculation of Laplacian eigenvalues (see [16] [17]) so the alternative approach presented here may be of some interest. Our calculations, based on probabilistic concepts and a symmetry condition, are generally simpler than those involving eigenvalues, and lead to closed form formulas which are also relatively simple. Now we will be interested in the non-regular bipartite case. It was shown in [15] that

Lemma 3. Whenever $\left(a,b\right)\in E$ , $a\in V_1$ and $b\in V_2$ we have

$E_a{T}_b=2\left|V_2\right|-1,$ (19)

and

$E_b{T}_a=2\left|V_1\right|-1.$ (20)

Equation (14) also applies in this case of non-regular edge-transitive graphs.

We start applying the previous result to the complete bipartite graph $K_{m,n}$ . Without loss of generality, let us assume that $m\ge n$ . Then, the partition of $V$ is $V_1=\left\{v\in V:d\left(v\right)=n\right\}$ and $V_2=\left\{v\in V:d\left(v\right)=m\right\}$ . Clearly $\left|V_1\right|=m$ and $\left|V_2\right|=n$ . By Lemma 2, we have, for $a\in V_1,b\in V_2$ :

$E_a{T}_b=2n-1\text{and}{E}_b{T}_a=2m-1.$

Thus, for $a\in V_1,b\in V_2$ :

$D\left(a,b\right)=2m-1.$ (21)

The graph $K_{m,n}$ has diameter 2, so in order to find all the remaining different values of the expected hitting times, we only have to find $E_a{T}_b$ when both $a,b\in V_1$ and when both $a,b\in V_2$ . Let us start with $a,b\in V_1$ . Because the graph is bipartite and has diameter 2, and conditioning on the first jump, it is clear that

$E_a{T}_b=1+E_c{T}_b,$

for $c\in V_2$ , i.e.,

$E_a{T}_b=1+2m-1=2m.$

For the reverse expected hitting time we get the same result, $E_b{T}_a=2m$ , so that for $a,b\in V_1$ we get

$D\left(a,b\right)=2m.$ (22)

A similar argument yields, for $a,b\in V_2$ that

$E_a{T}_b=1+2n-1=2n,$

and that in this case

$D\left(a,b\right)=2n.$ (23)

Putting together (21), (22) and (23), we obtain the following.

Proposition 4. For $m,n\ge 1$ we have

$HT\left(K_{m,n}\right)=m^2\left(m-1\right)+n^2\left(n-1\right)+nm\left(2\text{max}\left\{m,n\right\}-1\right).$ (24)

Proof. We first assume $m\ge n$ . There are $\frac{m\left(m-1\right)}{2}$ entries in the matrix $E$ that we must include in the computation of $HT\left(K_{m,n}\right)$ with value equal to $2m$ . Likewise, we must include $\frac{n\left(n-1\right)}{2}$ entries with the value $2n$ , and finally we must include $nm$ entries with the value $2m-1$ . Adding, we obtain the desired result, with $\text{max}\left\{m,n\right\}=m$ . If we assume $n\ge m$ we get the same result except that now $\text{max}\left\{m,n\right\}=n$ $•$

Formula (24) is symmetric in $n$ and $m$ , as it should, because $HT\left(K_{m,n}\right)=HT\left(K_{n,m}\right)$ . For the particular case $m=n$ we obtain $HT\left(K_{n,n}\right)=n^2\left(4n-3\right)$ . (this could also be found using (17) above.) On the other hand, the Kirchhoff index is $K\left(K_{n.n}\right)=4n-3$ , as can be seen in [18]. Therefore, in this case we have $HT\left(K_{n,n}\right)=\left|E\right|K\left(K_{n,n}\right)$ , which holds, as was pointed out in [9], because $K_{n,n}$ is walk-regular. Another interesting particular case is the star graph, $S_m=K_{m-1,1}$ , for which we get

$HT\left(K_{m-1,1}\right)={(m-1)}^2+\left(m-1\right)\left(2m-3\right)=\left(m-1\right)\left(m^2-m-1\right),$

which coincides with the value for $HT\left(S_m\right)$ obtained in [9]. So far, the graphs studied had diameter either 2 or 3. Now we will look at some graphs with diameter 4. One simple way to produce non-regular edge-transitive graphs is to introduce subdivision graphs: given a graph $G=\left(V,E\right)$ , its subdivision graph $G^{\prime }=\left(V^{\prime },E^{\prime }\right)$ is built by splitting every edge of $G$ with an extra vertex having degree 2. It is clear then that $G^{\prime }$ is bipartite, with one set of the partition being the 2-degree vertices, and the other set the original vertices in $V$ . Moreover, $\left|V^{\prime }\right|=\left|V\right|+\left|E\right|$ and $\left|E^{\prime }\right|=2\left|E\right|$ . We will denote by $T_i^{\text{'}}$ the hitting time of $i$ on the subdivision graph $G^{\prime }$ . Then we have:

Lemma 4. If $G$ is arc-transitive then $G^{\prime }$ is edge-transitive.

Proof. If $\varphi$ is the automorphism of $G$ that maps (either way) edges into edges, then the obvious extension of $\varphi$ on $V^{\prime }$ will also map any edge of $G^{\prime }$ into any edge of $G^{\prime }$ except maybe for the need of the application of a symmetry $•$

Lemma 2 allows us to conclude that

Proposition 5. For $i\in V,j\in V^{\prime }-V$ we have

$E_i{T^{\prime }}_j=2\left|E\right|-1,$ (25)

and

$E_j{T^{\prime }}_i=2\left|V\right|-1,$ (26)

and therefore

$D\left(i,j\right)=2\left|E\right|-1.$ (27)

For the next proposition, we will need the following result, which can be found in [19]:

Lemma 5. Multiplying by the same factor $r$ the resistance of every resistor in an electric network implies that the effective resistance between any two nodes of the network is multiplied by the same factor $r$ .

Proposition 6. For $i,j\in V$ , $\left(i,j\right)\in E$ , we have

$E_i{T^{\prime }}_j=E_j{T^{\prime }}_i=D\left(i,j\right)=4\left(\left|V\right|-1\right),$ (28)

More generally, for $i,j\in V$ , $\left(i,j\right)\in E$ , we have

$E_i{T^{\prime }}_j=E_j{T^{\prime }}_i=D\left(i,j\right)=4E_i{T}_j.$ (29)

Proof. In $G^{\prime }$ , all pairs of vertices in $V$ are at an even distance, therefore (14) applies and

$E_i{T^{\prime }}_j=\left|E^{\prime }\right|{R^{\prime }}_{ij}=4\left|E\right|R_{ij}=4E_i{T}_j,$

proving (29). In particular, if $d\left(i,j\right)=2$ in $V^{\prime }$ then $d\left(i,j\right)=1$ in $V$ , and thus $E_i{T}_j=\left|V\right|-1$ , proving (28).

Here we have used the fact that the introduction of the vertices splitting all edges amounts to doubling the value of all the resistances between neighboring vertices in $V$ , implying, by the lemma, the doubling of any effective resistance between vertices in $V$ , and thus ${R^{\prime }}_{ij}=2R_{ij}$ for $i,j\in V$ $•$

We will apply these formulas to a couple of examples. Let us first consider the complete graph $K_n=\left(V,E\right)$ and its subdivision ${K^{\prime }}_n=\left(V^{\prime },E^{\prime }\right)$ . Then we have

Proposition 7. The expected hitting time $E_i{T}_j$ in ${K^{\prime }}_n$ equals

(i) $n^2-n-1$ if $i\in V,j\in V^{\prime }-V$ and $d\left(i,j\right)=1$ ;

(ii) $2n-1$ if the roles of $i$ and $j$ in (i) are reversed;

(iii) $4\left(n-1\right)$ if $i,j\in V$ ;

(iv) $4n-3$ if $i\in V^{\prime }-V,j\in V$ , and $d\left(i,j\right)=3$ ;

(v) $n^2+n-3$ if the roles of $i$ and $j$ in (iv) are reversed;

(vi) $n^2-1$ if $i,j\in V^{\prime }-V$ and $d\left(i,j\right)=2$ ;

(vii) $n^2+n-2$ if $i,j\in V^{\prime }-V$ and $d\left(i,j\right)=4$ .

Proof. (i), (ii) and (iii) are direct consequences of propositions 4 and 5. For (iv) we condition on the first jump of the walk and obtain

$E_i{T}_j=1+\frac{1}{2}{E}_a{T}_j+\frac{1}{2}{E}_b{T}_j,$

where $a$ and $b$ are the two neighbors of $i$ . Now both $a,b\in V$ and $d\left(a,j\right)=d\left(b,j\right)=2$ , so we can apply (iii) and get

$E_i{T}_j=1+E_a{T}_j=1+4\left(n-1\right).$

Now for (v), (vi) and (vii) we obtain a $3\times 3$ linear system, again conditioning on the first jump of the walk. If $i,j\in V^{\prime }-V$ with $d\left(i,j\right)=2$ we have

$E_i{T}_j=1+\frac{1}{2}{E}_a{T}_j+\frac{1}{2}{E}_b{T}_j,$

with $a,b\in V$ neighbors of $i$ , $d\left(a,j\right)=1$ , $d\left(b,j\right)=3.$ By (i), $E_a{T}_j=n^2-n-1$ so we can write

$E_i{T}_j=1+\frac{1}{2}\left(n^2-n-1\right)+\frac{1}{2}{E}_b{T}_j.$ (30)

Also,

$E_b{T}_j=1+\frac{2}{n-1}{E}_i{T}_j+\frac{n-3}{n-1}{E}_c{T}_j,$ (31)

where $c\in V^{\prime }-V$ and $d\left(c,j\right)=4$ . Finally

$E_c{T}_j=1+E_b{T}_j.$ (32)

Solving for $E_i{T}_j$ , $E_b{T}_j$ and $E_c{T}_j$ in the system determined by equations (30), (31) and (32) finishes the proof. $•$

With the results in the previous proposition, we can prove the following:

Proposition 8. For $n\ge 4$ we have

$\begin{array}{c}HT\left({K^{\prime }}_n\right)=n\left(n-1\right)\left(n^2-n-1\right)+4\left(n-1\right)\left(\begin{array}{c}n\\ 2\end{array}\right)+n\left(\begin{array}{c}n-1\\ 2\end{array}\right)\left(n^2-1\right)\\ +\left[\left(\begin{array}{c}\left(\begin{array}{c}n\\ 2\end{array}\right)\\ 2\end{array}\right)-n\left(\begin{array}{c}n-1\\ 2\end{array}\right)\right]\left(n^2+n-2\right)\\ +\left[\left(\begin{array}{c}n+\left(\begin{array}{c}n\\ 2\end{array}\right)\\ 2\end{array}\right)-\left(\begin{array}{c}\left(\begin{array}{c}n\\ 2\end{array}\right)\\ 2\end{array}\right)-3\left(\begin{array}{c}n\\ 2\end{array}\right)\right]\left(n^2+n-3\right).\end{array}$ (33)

$=\frac{n\left(n-1\right)\left(n^4+4n^3-5n^2-4\right)}{8}.$ (34)

Proof. Every edge in the original graph $K_n$ generates two pairs of vertices at distance 1 in ${K^{\prime }}_n$ , so there are $n\left(n-1\right)$ such pars of vertices, where the larger hitting time between them is $n^2-n-1$ , according to (i) and (ii) of the previous theorem. That takes care of the first summand of formula (33).

As far as pairs of vertices at distance 2 are concerned, there are $\left(\begin{array}{c}n\\ 2\end{array}\right)$ such pairs generated by all possible pairs of vertices in the original $K_n$ . The hitting time for these is $4\left(n-1\right)$ , given in (iii). In addition, we need to consider pairs of subdivision points of incident edges of the original graph $K_n$ which are at distance 2 in ${K^{\prime }}_n$ . The number of incident edges in $K_n$ is easily found by looking at a fixed vertex, which generates $\left(\begin{array}{c}n-1\\ 2\end{array}\right)$ such incident pairs of edges, and then multiplying by the $n$ possible choices of the pivot vertex, for a total of $n\left(\begin{array}{c}n-1\\ 2\end{array}\right)$ pairs of subdivision points at distance 2 in ${K^{\prime }}_n$ , whose hitting time between them is $n^2-1$ by (vi). This justifies the second and third summands in (33).

Next we look at vertices at distance 4 in ${K^{\prime }}_n$ . These are determined by all pairs of non-incident pairs of edges in $K_n$ , and their number is equal to the total number of pairs of edges minus the number of those which are incident, i.e., $\left(\begin{array}{c}\left(\begin{array}{c}n\\ 2\end{array}\right)\\ 2\end{array}\right)-n\left(\begin{array}{c}n-1\\ 2\end{array}\right)$ . For these, the value of the hitting time between them, either way, is the same, given by (vii), as $n^2+n-2$ . This is the argument for the fourth summand of (33).

Finally, pairs of vertices in ${K^{\prime }}_n$ at distance 3 are found by subtracting from the grand total $\left(\begin{array}{c}n+\left(\begin{array}{c}n\\ 2\end{array}\right)\\ 2\end{array}\right)$ , all other pairs of vertices found in this proof. For these, the larger hitting times are $n^2+n-3$ as (iv) and (v) show. This justifies the last summand in (33). Adding then all the products of possible hitting times and pairs of vertices where these values occur, we get (33), and then some algebra simplifies this formula to the final expression (34) $•$

The next example is the complete bipartite graph $K_{n,n}=\left(V,E\right)$ and its subdivision graph ${K^{\prime }}_{n,n}=\left(V^{\prime },E^{\prime }\right)$ . Conditioning, it is easy to see that in $K_{n,n}$ we have $E_i{T}_j=2n-1$ if $i$ and $j$ belong to different sets of the partition, and $E_i{T}_j=2n$ if $i$ and $j$ belong to the same partition set. Then we have:

Proposition 9. The expected hitting time $E_i{T}_j$ in ${K^{\prime }}_{n,n}$ equals

(i) $2n^2-1$ if $i\in V,j\in V^{\prime }-V$ and $d\left(i,j\right)=1$ ;

(ii) $4n-1$ if the roles of $i$ and $j$ in (i) are reversed;

(iii) $4\left(2n-1\right)$ if $i,j\in V$ , and $d\left(i,j\right)=2$ ;

(iv) $8n$ if $i,j\in V$ , and $d\left(i,j\right)=4$ ;

(v) $8n-1$ if $i\in V^{\prime }-V,j\in V$ and $d\left(i,j\right)=3$ ;

(vi) $2n^2+4n-1$ if the roles of $i$ and $j$ in (v) are reversed;

(vii) $2n^2+2n$ if $i,j\in V^{\prime }-V$ and $d\left(i,j\right)=2$ ;

(viii) $2n^2+4n$ if $i,j\in V^{\prime }-V$ and $d\left(i,j\right)=4$ .

Proof. (i) and (ii) are immediately derived from proposition 4; (iii) and (iv) follow from proposition 5. Now for (v) we condition on the first jump of the walk to obtain

$E_i{T}_j=1+\frac{1}{2}{E}_a{T}_j+\frac{1}{2}{E}_b{T}_j,$ (35)

with $a,b\in V$ the neighbors of $i$ and $d\left(a,j\right)=4$ , $d\left(b,j\right)=2$ . We then use (iii) and (iv) in (35) to conclude

$E_i{T}_j=1+\frac{1}{2}4\left(2n-1\right)+\frac{1}{2}8n=8n-1.$

For the three remaining cases, we condition on the first jump in order to obtain a $3\times 3$ linear system. Indeed, if $i,j\in V^{\prime }-v$ and $d\left(i,j\right)=2$ we have

$E_i{T}_j=1+\frac{1}{2}{E}_a{T}_j+\frac{1}{2}{E}_b{T}_j,$

where $a,b\in V$ are the neighbors of $i$ and $d\left(a,j\right)=1$ , $d\left(b,j\right)=3$ . Using (i) we get then

$E_i{T}_j=1+\frac{1}{2}\left(2n^2-1\right)+\frac{1}{2}{E}_b{T}_j.$ (36)

Also,

$E_b{T}_j=1+\frac{1}{n}{E}_i{T}_j+\frac{n-1}{n}{E}_c{T}_j,$ (37)

where $c\in V^{\prime }-V$ and $d\left(c,j\right)=4$ . Finally,

$E_c{T}_j=1+E_b{T}_j.$ (38)

Solving the system determined by (36), (37) and (38) finishes the proof. $•$

With the results of the previous theorem we can prove the following

Proposition 10. For $n\ge 2$

$\begin{array}{c}HT\left({K^{\prime }}_{n,n}\right)=2n^2\left(2n^2-1\right)+4\left(2n-1\right)n^2+2n\left(\begin{array}{c}n\\ 2\end{array}\right)\left(2n^2+2n\right)\\ +\left[\left(\begin{array}{c}{n}^2\\ 2\end{array}\right)-2n\left(\begin{array}{c}n\\ 2\end{array}\right)\right]\left(2n^2+4n\right)+8n^2\left(n-1\right)\\ +\left[\left(\begin{array}{c}2n+n^2\\ 2\end{array}\right)-\left(\begin{array}{c}{n}^2\\ 2\end{array}\right)-3n^2-n\left(n-1\right)\right]\left(2n^2+4n-1\right)\end{array}$ (39)

$=n^6+6n^5+5n^4+6n^3-2n^2-12n^2.$ (40)

Proof. Every edge in the original graph $K_{n,n}$ generates two pairs of vertices at distance 1 in ${K^{\prime }}_{n,n}$ , so there are $2n^2$ such pars of vertices, where the larger hitting time between them is $2n^2-1$ , according to (i) and (ii) of the previous theorem. That takes care of the first summand in (39).

As for pairs of vertices at distance 2, we see that there are $n^2$ such pairs generated by the endpoints of all edges in the original $K_{n,n}$ . The hitting time for these is $4\left(2n-1\right)$ , given in (iii). In addition, we need to consider pairs of subdivision points of incident edges of the original graph $K_{n,n}$ which are at distance 2 in ${K^{\prime }}_n$ . The number of incident edges in $K_{n,n}$ is easily found by looking at a fixed vertex, which generates $\left(\begin{array}{c}n\\ 2\end{array}\right)$ such incident pairs of edges, and then multiplying by the $2n$ possible choices of the pivot vertex, for a total of $2n\left(\begin{array}{c}n\\ 2\end{array}\right)$ pairs of subdivision points at distance 2 in ${K^{\prime }}_{n,n}$ , whose hitting time between them is $2n^2+2n$ by (vii). This justifies the second and third summands in (39).

Next we look at vertices at distance 4 in ${K^{\prime }}_{n,n}$ . Some are determined by all pairs of non-incident pairs of edges in $K_{n,n}$ , and their number is equal to the total number of pairs of edges minus the number of those which are incident, i.e., $\left(\begin{array}{c}{n}^2\\ 2\end{array}\right)-2n\left(\begin{array}{c}n\\ 2\end{array}\right)$ . For these, the value of the hitting time between them, either way, is the same, given by (viii), as $2n^2+4n$ . Also, pairs of points in the same part of the partition (of which there are $2\left(\begin{array}{c}n\\ 2\end{array}\right)=n\left(n-1\right)$ ) are at distance 2 in $K_{n,n}$ and at distance 4 in ${K^{\prime }}_{n,n}$ , and the hitting time between them is $8n$ , according to (iv). This is the argument for the fourth and fifth summands in (39).

Finally, pairs of vertices in ${K^{\prime }}_{n,n}$ at distance 3 are found by subtracting from the grand total $\left(\begin{array}{c}2n+n^2\\ 2\end{array}\right)$ , all other pairs of vertices found in this proof. For these,

the larger hitting times are $n^2+4n-1$ as (v) and (vi) show. This justifies the last of (39). Then some algebra yields the final expression (40). $•$

Remark 1. For $n=2$ , our formula produces $HT\left({K^{\prime }}_{2,2}\right)=336$ , and we have that ${K^{\prime }}_{2,2}=C_8$ , the 8-cycle. It is known that $HT\left(C_n\right)=\left|E\right|K\left(C_8\right)=\frac{1}{12}{n}^2\left(n^2-1\right)$ , and for $n=8$ this yields $HT\left(C_8\right)=336$ , in agreement with the value found for $HT\left({K^{\prime }}_{2,2}\right)$ . In [9] the value of $HT\left(C_n\right)$ is wrongly reported as twice its correct value.

Remark 2. Formula (29) is shown in [20], for general graphs, using a spectral approach. That approach could have been used to find the expected hitting times on our subdivision graphs in terms of the hitting times on the original graphs, but we prefer the simple methods used here.

4. Conclusions

In this article, we have given a new upper bound for the hitting time index in terms of the Kirchhoff index and a new degree-weighted Kirchhoff index. This upper bound is better than or non-comparable to other bounds found in the literature. We have also worked with some families of graphs with diameters 2, 3 and 4, endowed with edge-transitivity, a form of symmetry weaker than edge-transitivity, that allows us to obtain, with probabilistic arguments, closed-form formulas for the hitting time index of these graphs. Our results deepen the understanding of the fairly recent $HT$ index, showing a new relationship with other Kirchhoffian indices and enlarging the universe of graphs whose $HT$ indices can be found with closed-form formulas.

Conflicts of Interest

The authors declare that there is no conflict of interest regarding this article.

References

[1]	Buckley, F. and Harary, F. (1990) Distance in Graphs. Addison-Wesley.
[2]	Bonchev, D., Balaban, A.T., Liu, X. and Klein, D.J. (1994) Molecular Cyclicity and Centricity of Polycyclic Graphs. I. Cyclicity Based on Resistance Distances or Reciprocal Distances. International Journal of Quantum Chemistry, 50, 1-20.[CrossRef]
[3]	Wiener, H. (1947) Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society, 69, 17-20.[CrossRef] [PubMed]
[4]	Grinstead, M. and Snell, J.L. (1997) Introduction to Probability. 2nd Edition, American Mathematical Society.
[5]	Palacios, J.L. (2000) Resistance Distance in Graphs and Random Walks. International Journal of Quantum Chemistry, 81, 29-33.[CrossRef]
[6]	Doyle, P. and Snell, J. (1984) Random Walks and Electric Networks. American Mathematical Society.[CrossRef]
[7]	Chandra, A.K., Raghavan, P., Ruzzo, W.L. and Smolensky, R. (1989) The Electrical Resistance of a Graph Captures Its Commute and Cover Times. Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing—STOC’89, Seattle, 14-17 May 1989, 574-586.[CrossRef]
[8]	Camby, E., Caporossi, G., Paiva, M.H.M. and Segatto, M.E.V. (2017) Expected Distance Based on Random Walks. Journal of Mathematical Chemistry, 56, 618-629.[CrossRef]
[9]	Palacios, J.L. (2024) A New Probabilistic Molecular Index. Match Communications in Mathematical and in Computer Chemistry, 93, 499-507.[CrossRef]
[10]	Palacios, J.L. and Santamarı́a, A. (2025) Some New Results for the Hitting Time Index. Match Communications in Mathematical and in Computer Chemistry, 94, 427-445.[CrossRef]
[11]	Ergotić, S.M. and Gottwald, K.K. (2025) Graphs That Preserve Kirchhoff Index after the Removal of a Vertex. Boletín de la Sociedad Matemática Mexicana, 31, Article No. 88.[CrossRef]
[12]	Chen, H. and Zhang, F. (2007) Resistance Distance and the Normalized Laplacian Spectrum. Discrete Applied Mathematics, 155, 654-661.[CrossRef]
[13]	Gutman, I., Feng, L. and Yu, L. (2012) Degree Resistance Distance of Unicyclic Graphs. Transactions on Combinatorics, 1, 27-40.
[14]	Palacios, J.L., Gómez, E. and Del Río, M. (2014) Hitting Times of Walks on Graphs through Voltages. Journal of Probability, 2014, Article ID: 852481.
[15]	Palacios, J. and Renom, J. (1998) Random Walks on Edge Transitive Graphs. Statistics & Probability Letters, 37, 29-34.[CrossRef]
[16]	Gao, X., Luo, Y. and Liu, W. (2011) Resistance Distances and the Kirchhoff Index in Cayley Graphs. Discrete Applied Mathematics, 159, 2050-2057.[CrossRef]
[17]	Wang, Y., Zhang, Q. and Yuan, K. (2025) Kirchhoff Indices of Cayley Graphs on . Applied Mathematics and Computation, 489, Article ID: 129132.[CrossRef]
[18]	Bapat, R.B., Karimi, M. and Liu, J. (2017) Kirchhoff Index and Degree Kirchhoff Index of Complete Multipartite Graphs. Discrete Applied Mathematics, 232, 41-49.[CrossRef]
[19]	Palacios, J.L. (2003) A Probabilistic Proof of an Electric Network Property. Ciencia, 11, 252-253.
[20]	Chen, H. (2017) Hitting Times for Random Walks on Subdivision and Triangulation Graphs. Linear and Multilinear Algebra, 66, 117-130.[CrossRef]