# Average hitting times in some $f$-equitable graphs

Yusaku Nishimura  School of Fundamental Science and Engineering, Waseda
University, Tokyo 169-8555, Japan<EMAIL_ADDRESS>
###### Abstract.

It is known that the average hitting times of simple random walks from any
vertex to any other vertex in distance-regular graphs are determined by their
intersection array. In this paper, we introduce a new graph classification
called $f$-equitable, utilizing both the equitable partition and the function
$f$, which represents a generalization of distance-regular graphs. We
determine the average hitting times from any vertex to any other vertex in
$f$-equitable graphs by using their parameter referred to as the quotient
matrix. Furthermore, we prove that there is some function $f$ such that the
Cartesian product of two strongly regular graphs is $f$-equitable. We then
calculate the quotient matrix for these graphs and determine the average
hitting times from any vertex to any other vertex in these graphs. In the same
manner, we determine the average hitting times on some generalized Paley
graphs.

##  1\. Introduction

A random walk on a graph is a stochastic process that moves randomly from
vertex to vertex along edges. Specifically, when each vertex is chosen with
equal probability during a random walk, it is referred to as a simple random
walk. For any given vertices $u$ and $v$ in a graph, the hitting time from
vertex $u$ to vertex $v$ is defined as the number of steps required to reach
vertex $v$ for the first time in a simple random walk starting from vertex
$u$. The expected value of the hitting times from vertex $u$ to vertex $v$ is
called the average hitting time from $u$ to $v$ and is denoted as
$H(G;(v,u))$. We define $H(G;(v,v))=0$.

It is known that we can compute the average hitting time between any two
vertices easily in certain types of graphs. A notable example is distance-
regular graphs, which belong to a class of graphs with high symmetry. Biggs
[1], Devroye and Sbihi [3], and Van Slijpe [9] independently demonstrated that
the average hitting times between any two vertices in a distance-regular graph
can be computed solely using the intersection array of the graph, which is a
set of parameters defining the distance-regular graph. In this paper, we
propose a new graph classification denoted as $f$-equitable, which is a
generalization of distance-regular graphs. The detailed definition of
$f$-equitable is given in Section 3.

In the following, we denote $\vec{\mathbf{1}}$ as the all-one vector and $I$
as the identity matrix. We determine the average hitting time from any vertex
to any vertex in an $f$-equitable graph by using its parameter, denoted as the
quotient matrix.

######  Theorem 1.1.

Let $G$ be an $f$-equitable graph with the quotient matrix $Q$ and valency
$k$, where the range of the function $f$ is $\\{x_{0},x_{1},\ldots,x_{r}\\}$,
and $Q$ is indexed in the order of $\\{x_{0},x_{1},\ldots,x_{r}\\}$. Let
$h_{x_{0}}=0$, and we define $h_{x_{i}}$ as follows:

$\displaystyle\vec{H}$ $\displaystyle=(h_{x_{1}},h_{x_{2}},\ldots,h_{x_{r}})$
$\displaystyle=-\vec{\mathbf{1}}\left(\frac{1}{k}Q^{-}-I\right)^{-1},$

where $Q^{-}$ is the submatrix obtained by removing the $x_{0}$th row and the
$x_{0}$th column from $Q$. Then, for any vertices $u$ and $v$ in $G$,

$H(G;(v,u))=h_{f(v,u)}.$

1.1 implies that if $G$ is $f$-equitable, then the average hitting time
between any two vertices in $G$ is determined using only the quotient matrix
and the function $f$. Using this method, we can calculate the average hitting
time in the Cartesian product of any two strongly regular graphs and specific
generalized Paley graphs using only these parameters, which was previously
unknown. In the same manner, the detailed definitions of these graphs and
parameters are provided in Sections 4, 5 and 6.

This paper is organized as follows. In Section 2, we provide the definition of
an equitable partition and discuss some of its properties. In Section 3, we
define $f$-equitable and present the proof for 1.1. In Section 4, we calculate
the average hitting time in distance-regular graphs by applying 1.1, and
confirm that the results are consistent with those previously obtained. In
Sections 5 and 6, we calculate the average hitting time in the Cartesian
product of two strongly regular graphs and specific generalized Paley graphs,
respectively. The actual calculations were performed using Mathematica [5].

##  2\. Definition of an equitable partition and some properties

In the following, $N_{G}(v)$ denotes the neighbor set of vertex $v$ in graph
$G$, and $\deg_{G}(v)$ denotes the degree of $v$. When $G$ is understood, we
omit it and write $N(v)$ and $\deg(v)$, respectively. We also denote $u\sim v$
if vertices $u$ and $v$ are adjacent.

### Definition and some properties of an equitable partition

Let $G$ be a graph and let $P=\\{V_{0},V_{1},\ldots,V_{r}\\}$ be a partition
of the vertex set of $G$.

######  Definition 2.1 (Equitable partition [8]).

The partition $P$ is called an equitable partition if, for all integers $i$
and $j$ such that $0\leq i,j\leq r$ and for all vertices $u$ and $v$ in
$V_{j}$, $|N(u)\cap V_{i}|=|N(v)\cap V_{i}|$ holds.

######  Definition 2.2 (Quotient matrix).

Let $P$ be an equitable partition of $G$. A matrix $q_{ij}=|N(v)\cap V_{i}|$,
where $v$ is for any vertex in $V_{j}$, is called a quotient matrix of $P$.

We can state some properties of the quotient matrix of an equitable partition.

######  Lemma 2.1.

Let $G$ be a graph, and let $P=\\{V_{0},V_{1},\ldots,V_{r}\\}$ be an equitable
partition of $G$ with quotient matrix $q_{ij}$.

$v\in V_{j}\Longrightarrow\deg(v)=\sum_{i=0}^{r}q_{ij}.$

###### Proof.

Define $V$ as the vertex set of $G$.

$\displaystyle\deg(v)$ $\displaystyle=|N(v)\cap V|$
$\displaystyle=\sum_{i=0}^{r}|N(v)\cap V_{i}|.$

From the definition of an equitable partition and $q_{ij}$,

$v\in V_{j}\Longrightarrow\sum_{i=0}^{r}|N(v)\cap
V_{i}|=\sum_{i=0}^{r}q_{ij}.$

∎

######  Lemma 2.2.

Let $G$ be a graph, and let $P=\\{V_{0},V_{1},\ldots,V_{r}\\}$ be an equitable
partition of $G$ with quotient matrix $q_{ij}$.

$|V_{i}|q_{ji}=|V_{j}|q_{ij}.$

###### Proof.

By counting the edges between $V_{i}$ and $V_{j}$ in two different ways, we
obtain this lemma. ∎

### Random walk on a graph with equitable partition

Let us consider a simple random walk on graph $G$ with an equitable partition
$P=\\{V_{0},V_{1},\ldots,V_{r}\\}$. Let $X_{0}=x$ be the starting vertex of a
simple random walk on $G$, and let $X_{t}$ be a random variable representing
the vertex reached after $t$ steps in the random walk. Similarly, let
$Y_{0}=V_{p_{0}}\ni X_{0}$ be the starting partition of the simple random walk
on $G$, and let $Y_{t}=V_{p_{t}}\ni X_{t}$ be the random variable representing
the partition reached after $t$ steps in the random walk. Then, $Y_{t}$ also
represents a stochastic process that moves randomly from $V_{j}$ to $V_{i}$,
where $V_{i}$ and $V_{j}$ are elements of $P$.

Since this partition $P$ is equitable, we can compute the transition
probabilities using the quotient matrix of $P$. Let us denote
$Pr(Y_{t}=V_{i}\mid Y_{t-1}=V_{j})$ as the probability of $Y_{t}=V_{i}$ given
that $Y_{t-1}=V_{j}$. Using 2.1,

(1) $Pr(Y_{t}=V_{i}\mid Y_{t-1}=V_{j})=\frac{|N(X_{t-1})\cap
V_{i}|}{\deg(X_{t-1})}=\frac{q_{ij}}{\sum_{l=0}^{r}q_{lj}}.$

We can define the hitting time from $V_{j}$ to $V_{i}$, which is similar to
the hitting time from vertex to vertex. For any integers $i$ and $j$ such that
$0\leq i,j\leq r$, we define the hitting time from $V_{j}$ to $V_{i}$ as the
number of steps required to reach any vertex $v\in V_{i}$ for the first time
in a simple random walk starting from any vertex $u\in V_{j}$. We also define
the average hitting time from $V_{j}$ to $V_{i}$ as the expected value of the
hitting times from $V_{j}$ to $V_{i}$, denoted as $H((G,P);(i,j))$. Because
Equation 1 shows that the transition probability $Pr(Y_{t}=V_{i}\mid
Y_{t-1}=V_{j})$ is independent of the choice of $u\in V_{j}$ and $v\in V_{i}$,
$H((G,P);(i,j))$ is well-defined. Similar to $H(G;(v,v))$, we define
$H((G,P);(i,i))=0$.

In the following, we denote $T_{G,P}$ as the transition probability matrix
from $V_{j}$ to $V_{i}$, where $P=\\{V_{0},\ldots,V_{r}\\}$ and its $ij$-entry
as

$t(G,P)_{ij}=\frac{q_{ij}}{\sum_{k=0}^{r}q_{kj}}.$

When $G$ and $P$ are clear, we omit them and write $T$ and $t_{ij}$.

##  3\. Definition of $f$-equitable and proof of 1.1

In this section, we first provide the definitions of $f$-equitable. Following
that, we give a proof of 1.1.

First, we define a stabilized equitable partition, which is useful for
considering the average hitting time from any vertex to a specific vertex.

######  Definition 3.1 (Stabilized equitable partition).

Let $G$ be a graph and let $P=\\{V_{0},V_{1},\ldots,V_{r}\\}$ be its equitable
partition. $P$ is called a stabilized equitable partition centered on vertex
$o$ if $V_{0}=\\{o\\}$.

When $P$ is a stabilized equitable partition centered on vertex $o$, the
average hitting time from any vertex to $o$ can be calculated using
$H((G,P);(0,i))$.

######  Lemma 3.1.

Let $G$ be a graph and $P=\\{V_{0}=\\{o\\},V_{1},\ldots,V_{r}\\}$ denote its
stabilized equitable partition centered on vertex $o$. For any vertex $v$ in
$V_{i}$,

$H(G;(o,v))=H((G,P);(0,i)).$

###### Proof.

From the definition, the average hitting time from $V_{i}$ to $V_{0}$
represents the average hitting time from any vertex $u\in V_{i}$ to $v\in
V_{0}$. In this case, since $V_{0}=\\{o\\}$, $v\in V_{0}$ means $v=o$.
Therefore, $H(G;(o,v))=H((G,P);(0,i))$. ∎

We can compute $H((G,P);(0,i))$ using the transition probability matrix
$t_{ij}$.

######  Theorem 3.1.

Let $T^{-}$ be the submatrix obtained by removing the $0$th row and the $0$th
column from $t_{ij}$. Then,

$\displaystyle\vec{H}$
$\displaystyle=(H((G,P);(0,1)),H((G,P);(0,2)),\ldots,H((G,P);(0,r)))$
$\displaystyle=-\vec{\mathbf{1}}(T^{-}-I)^{-1}.$

###### Proof.

Similar to the equations formulated for the average hitting time from vertex
to vertex, equations can also be formulated for $H((G,P);(0,i))$ as follows:

$\displaystyle H((G,P);(0,i))$
$\displaystyle=\sum_{k=0}^{r}(1+H((G,P);(0,k)))t_{ki}$
$\displaystyle=1+\sum_{k=0}^{r}H((G,P);(0,k))t_{ki}.$

When considering this equation for all $i$, we obtain
$\vec{H}T^{-}+\vec{\mathbf{1}}=\vec{H}$ and, by transforming the equation,

$\vec{H}=-\vec{\mathbf{1}}(T^{-}-I)^{-1}.$

∎

3.1 implies that if $P$ is a stabilized equitable partition centered on vertex
$o$, then we can compute $H(G;(o,u))$ for any vertex $u$ in $G$ using the
transition probability matrix, which is calculated by the quotient matrix of
$P$.

This method can obviously compute only the average hitting time ending at a
specific vertex. However, in some graphs with high symmetry, we can compute
the average hitting time from any vertex to any vertex using this method. We
classify such graphs as $f$-equitable graphs, where $f$ is a function that
takes two vertices of a graph as arguments.

######  Definition 3.2 ($f$-equitable graph).

Let $G$ be a graph with the vertex set $V$, and let $f:V\times
V\mapsto\\{x_{0},x_{1},\ldots,x_{r}\\}$ be a function. Define
$F_{x_{i}}(o)=\\{v\in V\mid f(o,v)=x_{i}\\}$ as a subset of $V$, and let

$P_{o}=\\{F_{x_{0}}(o),F_{x_{1}}(o),\ldots,F_{x_{r}}(o)\\}$

be the partition of $V$, where $o$ is any vertex in $V$. $G$ is called an
$f$-equitable graph if, for all vertices $o$ in the graph $G$, $P_{o}$
satisfies the following three conditions:

  * •

$F_{x_{0}}(o)=\\{o\\}$;

  * •

$P_{o}$ is equitable;

  * •

the quotient matrix of $P_{o}$ does not depend on the choice of $o$.

Note that the quotient matrix of
$P_{o}=\\{F_{x_{0}}(o),F_{x_{1}}(o),\ldots,F_{x_{r}}(o)\\}$ is indexed by
$x_{0},x_{1},\ldots,x_{r}$. In the following, we denote the quotient matrix of
an $f$-equitable graph as the quotient matrix of $P_{o}$. Before the proof of
1.1, we give a simple property of an $f$-equitable graph.

######  Lemma 3.2.

Let $G$ be an $f$-equitable graph with the quotient matrix $Q$. Then, $G$ is a
regular graph with valency $\sum_{k=0}^{r}q_{x_{k}x_{0}}$, where
$q_{x_{i}x_{j}}$ is the entry of the $x_{i}$th row and $x_{j}$th column of
$Q$.

###### Proof.

From the definition of $f$-equitable, for all vertices $o$ in $G$, there
exists a stabilized equitable partition centered on $o$ and its quotient
matrix is $Q$. The sum of the column $x_{0}$ of $Q$ represents the degree of
$o$. Since $Q$ does not depend on the choice of $o$, neither does the degree
of $o$. Thus, the proof is completed. ∎

Then, we prove 1.1.

###### Proof of 1.1.

Define $F_{x_{i}}(v)=\\{u\in V\mid f(v,u)=x_{i}\\}$ as the subset of $V$ and
$P_{v}=\\{F_{x_{0}}(v),F_{x_{1}}(v),\ldots,F_{x_{r}}(v)\\}$ as the partition
of $G$. From the definition of $f$-equitable, $P_{v}$ is a stabilized
equitable partition centered on $v$ and its quotient matrix is $Q$. Since the
valency of $G$ is $k$, from Equation 1

$T_{G,P_{v}}=\frac{1}{k}Q.$

From 3.1,

$\displaystyle\vec{H^{\prime}}$
$\displaystyle=(H((G,P_{v});(x_{0},x_{1})),H((G,P_{v});(x_{0},x_{2})),\ldots,H((G,P_{v});(x_{0},x_{r})))$
$\displaystyle=-\vec{\mathbf{1}}(T_{G,P_{v}}^{-}-I)^{-1}$
$\displaystyle=-\vec{\mathbf{1}}\left(\frac{1}{k}Q^{-}-I\right)^{-1}$
$\displaystyle=\vec{H}.$

Therefore, $\vec{H}=\vec{H^{\prime}}$. Especially,

$h_{x_{i}}=H((G,P_{v});(x_{0},x_{i})),$

where $1\leq i\leq r$. From 3.1, for any vertex $u$ in $F_{x_{i}}(v)$,

$\displaystyle H(G;(v,u))=H((G,P_{v});(x_{0},x_{i})).$

From the definition of $F_{x_{i}}(v)$, $u\in F_{x_{i}}(v)$ if and only if
$f(v,u)=x_{i}$. Therefore, for any vertex $u$ not in $F_{x_{0}}(v)$ in $G$,

$\displaystyle H(G;(v,u))=H((G,P_{v});(x_{0},f(v,u)))=h_{f(v,u)}.$

Given that $F_{x_{0}}(v)=\\{v\\}$, $u\in F_{x_{0}}(v)$ if and only if $u=v$.
Hence,

$H(G;(v,u))=\begin{cases}0&f(v,u)=x_{0}\\\ h_{f(v,u)}&f(v,u)\neq
x_{0}\end{cases}.$

Since $h_{x_{0}}=0$, by organizing the conditions,

$H(G;(u,v))=h_{f(v,u)}.$

∎

In short, we can compute the average hitting time from any vertex to any
vertex in an $f$-equitable graph using the quotient matrix and the function
$f$. In the following, we denote

$\vec{H}(A)=-\vec{\mathbf{1}}(A^{-}-I)^{-1},$

where $A$ is square matrix indexed by $\\{x_{0},\ldots,x_{r}\\}$ and $A^{-}$
is the submatrix obtained by removing the $x_{0}$th row and the $x_{0}$th
column from $A$.

We will consider specific examples of $f$-equitable graphs for which we can
specify the quotient matrix.

##  4\. Average hitting time on a distance-regular graph

In this section, we determine the average hitting time of a distance-regular
graph using 1.1.

We define $d_{G}(u,v)$ as the distance between two vertices $u$ and $v$ in
graph $G$, representing the length of the shortest path connecting $u$ and
$v$, and define $d_{G}(v,v)=0$. We also define $\Delta_{G}$ as the diameter of
$G$, which is the maximum distance $d_{G}(u,v)$ among all pairs of vertices
$u$ and $v$ in $G$.

######  Definition 4.1 (Distance-regular graph [2]).

A $k$-regular graph $G$ is called distance-regular if there exist integers
$b_{i}$ and $c_{i}$, where $0\leq i\leq\Delta_{G}$, such that for any pair of
vertices $u$ and $v$ in the graph with a distance of $i$ between them, there
are precisely $c_{i}$ neighbors of $u$ in the set of vertices at a distance of
$i-1$ from $v$ and $b_{i}$ neighbors of $u$ in the set of vertices at a
distance of $i+1$ from $v$. This integer array, denoted as
$\\{b_{0}=k,b_{1},\ldots,b_{\Delta_{G}-1};c_{1}=1,c_{2},\ldots,c_{\Delta_{G}}\\}$,
is called the intersection array.

In fact, the distance-regular graph is a notable example of a
$d_{G}$-equitable graph.

######  Lemma 4.1.

$G$ is a distance-regular graph with the intersection array
$\\{b_{0}=k,\ldots,b_{\Delta_{G}-1};c_{1},\ldots,c_{\Delta_{G}}\\}$ if and
only if $G$ is a $d_{G}$-equitable graph with the following quotient matrix
$Q$:

$\displaystyle Q=\begin{pmatrix}0&1&0&\ldots&0\\\
k&k-b_{1}-c_{1}&c_{2}&\ldots&0\\\ 0&b_{1}&k-b_{2}-c_{2}&\ldots&0\\\
0&&\vdots&&0\\\
0&\ldots&\ldots&k-b_{\Delta_{G}-1}-c_{\Delta_{G}-1}&c_{\Delta_{G}}\\\
0&\ldots&\ldots&b_{\Delta_{G}-1}&k-b_{\Delta_{G}}-c_{\Delta_{G}}\\\
\end{pmatrix}.$

###### Proof.

Let $G$ be a distance-regular graph with the intersection array
$\\{b_{0}=k,\ldots,b_{\Delta_{G}-1};c_{1}=1,\ldots,c_{\Delta_{G}}\\}$. Define
$D_{i}(v)=\\{u\in V\mid d_{G}(v,u)=i\\}$ and partition
$P_{v}=\\{D_{0}(v),D_{1}(v),\ldots,D_{\Delta_{G}}(v)\\}$. From the definition
of distance-regular graphs, for any vertex $v\in G$,

(2) $u\in D_{j}(v)\Longrightarrow|N(u)\cap
D_{i}(v)|=\begin{cases}c_{i}&i=j-1\\\ k-b_{i}-c_{i}&i=j\\\ b_{i}&i=j+1\\\
0&\text{others}\\\ \end{cases}$

This implies $P_{v}$ is the equitable partition and its quotient matrix is $Q$
as follows:

$Q=\begin{pmatrix}0&1&0&\ldots&0\\\ k&k-b_{1}-c_{1}&c_{2}&\ldots&0\\\
0&b_{1}&k-b_{2}-c_{2}&\ldots&0\\\ 0&&\vdots&&0\\\
0&\ldots&\ldots&k-b_{\Delta_{G}-1}-c_{\Delta_{G}-1}&c_{\Delta_{G}}\\\
0&\ldots&\ldots&b_{\Delta_{G}-1}&k-b_{\Delta_{G}}-c_{\Delta_{G}}\\\
\end{pmatrix}$

Here, we can define any vertex in $G$ as $v$, and $Q$ is independent of the
choice of $v$. Furthermore, from the definition of $d_{G}$,
$D_{0}(v)=\\{v\\}$. Therefore, the distance-regular graph is a
$d_{G}$-equitable graph with the quotient matrix $Q$.

Conversely, let $G$ be a $d_{G}$-equitable graph with the quotient matrix $Q$.
From the definition of the quotient matrix, we also have Equation 2, and this
implies $G$ is a distance-regular graph with the intersection array
$\\{b_{0}=k,\ldots,b_{\Delta_{G}-1};c_{1},\ldots,c_{\Delta_{G}}\\}$. ∎

Using 1.1, we can compute the average hitting times in distance-regular
graphs.

######  Theorem 4.1.

Let $G$ be a distance-regular graph with intersection array
$\\{b_{0}=k,b_{1},\ldots,b_{\Delta_{G}-1};c_{1}=1,\ldots,c_{\Delta_{G}}\\}$.
Consider vertices $u$ and $v$ in this distance-regular graph $G$, and let $Q$
be the quotient matrix of $G$ as a $d_{G}$-equitable graph. Then,

$H(G;(u,v))=h_{d_{G}(u,v)},$

where $\vec{H}(\frac{1}{k}Q)=(h_{1},h_{2},\ldots,h_{\Delta_{G}})$ and
$h_{0}=0$.

###### Proof.

From 1.1,

$H(G;(u,v))=h_{d_{G}(u,v)}.$

∎

4.1 was previously obtained independently by Biggs [1], Devroye and Sbihi [3],
and Van Slijpe [9], and they computed $\vec{H}(\frac{1}{k}Q)$.

######  Theorem 4.2 ([1, 3, 9]).

$h_{i}=\sum_{j=1}^{i}\frac{k}{k_{j-1}b_{j-1}}\sum_{l=j}^{\Delta_{G}}k_{l},$

where $k_{i}$ is an integer array defined for $0\leq i\leq\Delta_{G}$ such
that $k_{0}=1$ and $k_{i}=\frac{b_{i-1}}{c_{i}}k_{i-1}$.

##  5\. Average hitting times of Cartesian product of two strongly regular
graphs

In this section, we give a proof that if $G$ and $G^{\prime}$ are
$f$-equitable and $f^{\prime}$-equitable, respectively, then the Cartesian
product of $G$ and $G^{\prime}$ is $(f,f^{\prime})$-equitable, where
$(f,f^{\prime})$ is defined by $f$ and $f^{\prime}$. Using this result, we
calculate the average hitting time from any vertex to another on the Cartesian
product of two strongly regular graphs. Before the discussion, we define the
Cartesian product of two graphs.

######  Definition 5.1 (Cartesian product of two graphs).

Let $G$ and $G^{\prime}$ be graphs with vertices $V$ and $V^{\prime}$,
respectively. The Cartesian product of $G$ and $G^{\prime}$ is defined by the
vertex set $V\times V^{\prime}$, and the vertices $(u,u^{\prime})$ and
$(v,v^{\prime})$ in $V\times V^{\prime}$ are adjacent if

$((u=v)\land(u^{\prime}\sim v^{\prime}))\lor((u\sim
v)\land(u^{\prime}=v^{\prime})).$

In the following, we define $G\times G^{\prime}$ as the Cartesian product of
two graphs $G$ and $G^{\prime}$.

### Cartesian product of two graphs that are $f$-equitable and
$f^{\prime}$-equitable

In this subsection, we prove the following theorem.

######  Theorem 5.1.

Let $G$ be an $f$-equitable graph with the quotient matrix $Q$ and vertex set
$V$. Similarly, let $G^{\prime}$ be an $f^{\prime}$-equitable graph with the
quotient matrix $Q^{\prime}$ and vertex set $V^{\prime}$. Then, $G\times
G^{\prime}$ is an $(f,f^{\prime})$-equitable graph with the quotient matrix

$Q\otimes I_{r^{\prime}+1}+I_{r+1}\otimes Q^{\prime},$

where $r+1,r^{\prime}+1$ is the size of $Q,Q^{\prime}$, respectively, and
$(f,f^{\prime})$ is a function such that

$\displaystyle(f,f^{\prime}):(V\times V^{\prime})\times(V\times V^{\prime})$
$\displaystyle\mapsto f(V\times V)\times f^{\prime}(V^{\prime}\times
V^{\prime})$ $\displaystyle((u,u^{\prime}),(v,v^{\prime}))$
$\displaystyle\mapsto(f(u,v),f^{\prime}(u^{\prime},v^{\prime})).$

To prove 5.1, we establish the following lemma.

######  Lemma 5.1.

Let $G,G^{\prime}$ be graphs with equitable partitions
$P=\\{V_{0},V_{1},\ldots,V_{r}\\}$ and
$P^{\prime}=\\{V^{\prime}_{0},\ldots,V^{\prime}_{r^{\prime}}\\}$,
respectively. The quotient matrices of these partitions are denoted as $Q$ and
$Q^{\prime}$, respectively. Then,

$P\times P^{\prime}=\\{(V_{i},V^{\prime}_{j})\mid 0\leq i\leq r,0\leq j\leq
r^{\prime}\\}$

is an equitable partition of $G\times G^{\prime}$. The quotient matrix of
$P\times P^{\prime}$ is given by $Q\otimes I_{r^{\prime}+1}+I_{r+1}\otimes
Q^{\prime}$.

###### Proof.

Using the definition of the Cartesian product, we have the following equation:

$N_{G\times
G^{\prime}}((v,v^{\prime}))=(N_{G}(v),v^{\prime})\cup(v,N_{G^{\prime}}(v^{\prime})).$

Therefore,

$\displaystyle|N_{G\times
G^{\prime}}((v,v^{\prime}))\cap(V_{i},V^{\prime}_{j})|$
$\displaystyle=|((N_{G}(v),v^{\prime})\cup(v,N_{G^{\prime}}(v^{\prime})))\cap(V_{i},V^{\prime}_{j})|$
$\displaystyle=|((N_{G}(v),v^{\prime})\cap(V_{i},V^{\prime}_{j}))\cup((v,N_{G^{\prime}}(v^{\prime}))\cap(V_{i},V^{\prime}_{j}))|$
$\displaystyle=|(N_{G}(v),v^{\prime})\cap(V_{i},V^{\prime}_{j})|+|(v,N_{G^{\prime}}(v^{\prime}))\cap(V_{i},V^{\prime}_{j})|.$

Since both $P$ and $P^{\prime}$ are equitable partitions, for any integers $k$
and $l$ such that $0\leq k\leq r$ and $0\leq l\leq r^{\prime}$, if
$(v,v^{\prime})\in(V_{k},V^{\prime}_{l})$, then

$\displaystyle|(N_{G}(v),v^{\prime})\cap(V_{i},V^{\prime}_{j})|=\begin{cases}0&j\neq
l\\\ q_{ik}&j=l\end{cases},$
$\displaystyle|(v,N_{G^{\prime}}(v^{\prime}))\cap(V_{i},V^{\prime}_{j})|=\begin{cases}0&i\neq
k\\\ q^{\prime}_{jl}&i=k\end{cases}.$

Therefore,

$\displaystyle|N_{G\times
G^{\prime}}((v,v^{\prime}))\cap(V_{i},V^{\prime}_{j})|$
$\displaystyle=|(N_{G}(v),v^{\prime})\cap(V_{i},V^{\prime}_{j})|+|(v,N_{G^{\prime}}(v^{\prime}))\cap(V_{i},V^{\prime}_{j})|$
$\displaystyle=\delta_{ik}q^{\prime}_{jl}+\delta_{jl}q_{ik},$

where $\delta_{ij}$ is the Kronecker delta defined as

$\delta_{ij}=\begin{cases}1&i=j\\\ 0&i\neq j\end{cases}.$

This equation implies that the partition $P\times P^{\prime}$ is an equitable
partition. The quotient matrix of $P\times P^{\prime}$ is indexed by
$\\{0,1,\ldots,r\\}\times\\{0,1,\ldots,r^{\prime}\\}$, and its
$(i,j)(k,l)$-entry is denoted as
$\delta_{ik}q^{\prime}_{jl}+\delta_{jl}q_{ik}$. We can also represent this
matrix as $Q\otimes I_{r^{\prime}+1}+I_{r+1}\otimes Q^{\prime}$. ∎

Using 5.1, we prove 5.1.

###### Proof of 5.1.

Let $V,V^{\prime}$ be the sets of vertices of $G$ and $G^{\prime}$,
respectively, and let $\\{x_{0},x_{1},\ldots,x_{r}\\}$ and
$\\{x^{\prime}_{0},x^{\prime}_{1},\ldots,x^{\prime}_{r^{\prime}}\\}$ be the
sets of return values of the functions $f$ and $f^{\prime}$, respectively.
Define

$F_{x_{i}}(v)=\\{u\in V\mid f(v,u)=x_{i}\\}$

as the subset of $V$ and

$P_{v}=\\{F_{x_{0}}(v)=\\{v\\},F_{x_{1}}(v),\ldots,F_{x_{r}}(v)\\}$

as the partition of $V$, where $v$ is for any vertex in $V$. Similarly, define

$F^{\prime}_{x^{\prime}_{i}}(v^{\prime})=\\{u^{\prime}\in V^{\prime}\mid
f^{\prime}(v^{\prime},u^{\prime})=x^{\prime}_{i}\\}$

as the subset of $V^{\prime}$ and

$P^{\prime}_{v^{\prime}}=\\{F^{\prime}_{x^{\prime}_{0}}(v^{\prime})=\\{v^{\prime}\\},F^{\prime}_{x^{\prime}_{1}}(v^{\prime}),\ldots,F^{\prime}_{x^{\prime}_{r^{\prime}}}(v^{\prime})\\}$

as the partition of $V^{\prime}$, where $v^{\prime}$ is for any vertex in
$V^{\prime}$. From the definition of $f$-equitable graphs and
$f^{\prime}$-equitable graphs, for all vertices $v\in G$ and $v^{\prime}\in
G^{\prime}$, both $P_{v}$ and $P^{\prime}_{v^{\prime}}$ are stabilized
equitable partitions centered on $v$ and $v^{\prime}$, respectively, and their
quotient matrices are $Q,Q^{\prime}$, respectively. From 5.1, $P_{v}\times
P^{\prime}_{v^{\prime}}$ is also a stabilized equitable partition centered on
$(v,v^{\prime})$ and its quotient matrix is $Q\otimes
I_{r^{\prime}+1}+I_{r+1}\otimes Q^{\prime}$, which does not depend on the
choice of $v$ and $v^{\prime}$. Here, let
$(F,F^{\prime})_{(i,j)}(v,v^{\prime})$ be a subset of $V\times V^{\prime}$
such that

$(F,F^{\prime})_{(i,j)}(v,v^{\prime})=\\{(u,u^{\prime})\in V\times
V^{\prime}\mid(f,f^{\prime})((v,v^{\prime}),(u,u^{\prime}))=(i,j)\\},$

and let

$P_{v,v^{\prime}}(f,f^{\prime})=\\{(F,F^{\prime})_{(i,j)}(v,v^{\prime})\mid
0\leq i\leq r,0\leq j\leq r^{\prime}\\}$

be a partition of $G\times G^{\prime}$. Since $(u,u^{\prime})$ is in
$(F_{x_{i}}(v),F^{\prime}_{x^{\prime}_{j}}(v^{\prime}))$ if and only if
$f(v,u)=x_{i}$ and $f^{\prime}(v^{\prime},u^{\prime})=x^{\prime}_{j}$ hold, we
obtain $P_{v,v^{\prime}}(f,f^{\prime})=P_{v}\times P^{\prime}_{v^{\prime}}$.
Therefore, $G\times G^{\prime}$ is $(f,f^{\prime})$-equitable with quotient
matrix $Q\otimes I_{r^{\prime}+1}+I_{r+1}\otimes Q^{\prime}$. ∎

From 5.1, if $G$ and $G^{\prime}$ are $f$-equitable and
$f^{\prime}$-equitable, respectively, and the quotient matrices of these
graphs are determined, then we can also determine the average hitting time in
$G\times G^{\prime}$.

### Application of 5.1 for Cartesian product of two strongly regular graphs

In this subsection, we calculate the average hitting time from any vertex to
another on the Cartesian product of two strongly regular graphs using only
their parameters by using 1.1 and 5.1.

First, we define a strongly regular graph.

######  Definition 5.2.

Graph $G$ is called a strongly regular graph if $G$ is a distance-regular
graph and the diameter of $G$ is $2$.

Because the diameter of a strongly regular graph is always $2$, its
intersection array is denoted as $\\{b_{0},b_{1};c_{1}=1,c_{2}\\}$. Using
this, the parameter of a strongly regular graph with order $n$ is generally
defined as $(n,k,a,c)$, where $k=b_{0}$ is the valency of the graph, $a$ is
$k-b_{1}-1$, and $c$ is $c_{2}$.

######  Corollary 5.1.

Let $G_{1},G_{2}$ be strongly regular graphs with parameters
$(n_{1},k_{1},a_{1},c_{1})$ and $(n_{2},k_{2},a_{2},c_{2})$, respectively, and
let the vertex sets of $G_{1}$ and $G_{2}$ be $V_{1}$ and $V_{2}$,
respectively. Define $(d_{G_{1}},d_{G_{2}})$ as the following function:

$\displaystyle(d_{G_{1}},d_{G_{2}}):(V_{1}\times V_{2})\times(V_{1}\times
V_{2})$ $\displaystyle\mapsto\\{0,1,2\\}\times\\{0,1,2\\}$
$\displaystyle(d_{G_{1}},d_{G_{2}})((u_{1},u_{2}),(v_{1},v_{2}))$
$\displaystyle\mapsto(d_{G_{1}}(u_{1},v_{1}),d_{G_{2}}(u_{2},v_{2})).$

Then, $G_{1}\times G_{2}$ is $(d_{G_{1}},d_{G_{2}})$-equitable with the
quotient matrix $Q$ as follows:

$\displaystyle Q$
$\displaystyle=\scalebox{0.7}{$\left(\begin{array}[]{ccccccccc}0&1&0&1&0&0&0&0&0\\\
k_{2}&a_{2}&c_{2}&0&1&0&0&0&0\\\ 0&-a_{2}+k_{2}-1&k_{2}-c_{2}&0&0&1&0&0&0\\\
k_{1}&0&0&a_{1}&1&0&c_{1}&0&0\\\
0&k_{1}&0&k_{2}&a_{1}+a_{2}&c_{2}&0&c_{1}&0\\\
0&0&k_{1}&0&-a_{2}+k_{2}-1&a_{1}-c_{2}+k_{2}&0&0&c_{1}\\\
0&0&0&-a_{1}+k_{1}-1&0&0&k_{1}-c_{1}&1&0\\\
0&0&0&0&-a_{1}+k_{1}-1&0&k_{2}&a_{2}-c_{1}+k_{1}&c_{2}\\\
0&0&0&0&0&-a_{1}+k_{1}-1&0&-a_{2}+k_{2}-1&-c_{1}-c_{2}+k_{1}+k_{2}\\\
\end{array}\right)$}.$

###### Proof.

By 4.1, $G_{1}$ is $d_{G_{1}}$-equitable with the quotient matrix $Q_{1}$ and
$G_{2}$ is $d_{G_{2}}$-equitable with the quotient matrix $Q_{2}$, where

$\displaystyle Q_{1}$ $\displaystyle=\begin{pmatrix}0&1&0\\\
k_{1}&a_{1}&c_{1}\\\ 0&k_{1}-a_{1}-1&k_{1}-c_{1}\end{pmatrix},$ $\displaystyle
Q_{2}$ $\displaystyle=\begin{pmatrix}0&1&0\\\ k_{2}&a_{2}&c_{2}\\\
0&k_{2}-a_{2}-1&k_{2}-c_{2}\end{pmatrix}.$

By 5.1, $G_{1}\times G_{2}$ is also $(d_{G_{1}},d_{G_{2}})$-equitable with the
quotient matrix $Q_{1,2}$, where

$\displaystyle Q_{1,2}$ $\displaystyle=Q_{1}\otimes I_{3}+I_{3}\otimes Q_{2}$
$\displaystyle=\scalebox{0.7}{$\left(\begin{array}[]{ccccccccc}0&1&0&1&0&0&0&0&0\\\
k_{2}&a_{2}&c_{2}&0&1&0&0&0&0\\\ 0&-a_{2}+k_{2}-1&k_{2}-c_{2}&0&0&1&0&0&0\\\
k_{1}&0&0&a_{1}&1&0&c_{1}&0&0\\\
0&k_{1}&0&k_{2}&a_{1}+a_{2}&c_{2}&0&c_{1}&0\\\
0&0&k_{1}&0&-a_{2}+k_{2}-1&a_{1}-c_{2}+k_{2}&0&0&c_{1}\\\
0&0&0&-a_{1}+k_{1}-1&0&0&k_{1}-c_{1}&1&0\\\
0&0&0&0&-a_{1}+k_{1}-1&0&k_{2}&a_{2}-c_{1}+k_{1}&c_{2}\\\
0&0&0&0&0&-a_{1}+k_{1}-1&0&-a_{2}+k_{2}-1&-c_{1}-c_{2}+k_{1}+k_{2}\\\
\end{array}\right)$}.$

∎

Using 5.1, we can calculate the average hitting times between any pair of
vertices in the Cartesian product of two strongly regular graphs. However,
when dealing with general parameters $(n_{1},k_{1},a_{1},c_{1})$ and
$(n_{2},k_{2},a_{2},c_{2})$, the resulting equation becomes too long to
display in full. Therefore, we provide specific results for the case where
both graphs are identical, denoted as $G_{1}=G_{2}=G$.

######  Corollary 5.2.

Let $G$ be the strongly regular graph with parameters $(n,k,a,c)$. Then,

$\displaystyle H(G\times G;((u_{1},v_{1}),(u_{2},v_{2})))$
$\displaystyle=\begin{cases}0&(u_{1},v_{1})=(u_{2},v_{2})\\\
n^{2}-1&d_{G\times G}((u_{1},v_{1}),(u_{2},v_{2}))=1\\\
\frac{-c\left(n^{2}-1\right)(a-2k-1)+c^{2}\left(n^{2}-1\right)+k(k+n+1)}{c(-a+c+2k)}&(d_{G\times
G}((u_{1},v_{1}),(u_{2},v_{2}))=2)\land(i)\\\
\frac{-a\left(n^{2}+n-2\right)+c\left(n^{2}+n-2\right)+2kn^{2}+kn-4k+n^{2}-n}{-a+c+2k}&(d_{G\times
G}((u_{1},v_{1}),(u_{2},v_{2}))=2)\land(ii)\\\
\frac{c\left(-a\left(n^{2}+n-2\right)+k\left(2n^{2}+n-4\right)+n^{2}-1\right)+c^{2}\left(n^{2}+n-2\right)+k(k+n+1)}{c(-a+c+2k)}&d_{G\times
G}((u_{1},v_{1}),(u_{2},v_{2}))=3\\\
\frac{c\left(-a\left(n^{2}+n-2\right)+k\left(2n^{2}+n-4\right)+n^{2}+n-2\right)+c^{2}\left(n^{2}+n-2\right)+k(2k+n+2)}{c(-a+c+2k)}&d_{G\times
G}((u_{1},v_{1}),(u_{2},v_{2}))=4,\end{cases}$

where condition $(i)$ is $(u_{1}=u_{2})\lor(v_{1}=v_{2})$ and condition $(ii)$
is otherwise.

###### Proof.

By applying 5.1, we know that $G\times G$ is a $(d_{G},d_{G})$-equitable graph
with the quotient matrix $Q$ given as follows:

$Q={\scriptsize\left(\begin{array}[]{ccccccccc}0&1&0&1&0&0&0&0&0\\\
k&a&c&0&1&0&0&0&0\\\ 0&-a+k-1&k-c&0&0&1&0&0&0\\\ k&0&0&a&1&0&c&0&0\\\
0&k&0&k&2a&c&0&c&0\\\ 0&0&k&0&-a+k-1&a-c+k&0&0&c\\\
0&0&0&-a+k-1&0&0&k-c&1&0\\\ 0&0&0&0&-a+k-1&0&k&a-c+k&c\\\
0&0&0&0&0&-a+k-1&0&-a+k-1&-2c+2k\\\ \end{array}\right)}.$

From 1.1,

$\displaystyle\vec{H}$
$\displaystyle=(h_{(0,1)},h_{(0,2)},h_{(1,0)},h_{(1,1)},h_{(1,2)},h_{(2,0)},h_{(2,1)},h_{(2,2)})$
$\displaystyle=\vec{H}(\frac{1}{2k}Q)$
$\displaystyle=\left(\begin{array}[]{c}n^{2}-1\\\
\frac{-c\left(n^{2}-1\right)(a-2k-1)+c^{2}\left(n^{2}-1\right)+k(k+n+1)}{c(-a+c+2k)}\\\
n^{2}-1\\\
\frac{-a\left(n^{2}+n-2\right)+c\left(n^{2}+n-2\right)+2kn^{2}+kn-4k+n^{2}-n}{-a+c+2k}\\\
\frac{c\left(-a\left(n^{2}+n-2\right)+k\left(2n^{2}+n-4\right)+n^{2}-1\right)+c^{2}\left(n^{2}+n-2\right)+k(k+n+1)}{c(-a+c+2k)}\\\
\frac{-c\left(n^{2}-1\right)(a-2k-1)+c^{2}\left(n^{2}-1\right)+k(k+n+1)}{c(-a+c+2k)}\\\
\frac{c\left(-a\left(n^{2}+n-2\right)+k\left(2n^{2}+n-4\right)+n^{2}-1\right)+c^{2}\left(n^{2}+n-2\right)+k(k+n+1)}{c(-a+c+2k)}\\\
\frac{c\left(-a\left(n^{2}+n-2\right)+k\left(2n^{2}+n-4\right)+n^{2}+n-2\right)+c^{2}\left(n^{2}+n-2\right)+k(2k+n+2)}{c(-a+c+2k)}\\\
\end{array}\right)^{\top}.$

Then,

$H(G\times
G;((u_{1},v_{1}),(u_{2},v_{2})))=\begin{cases}0&(u_{1},v_{1})=(u_{2},v_{2})\\\
h_{(d_{G}(u_{1},u_{2}),d_{G}(v_{1},v_{2}))}&(u_{1},v_{1})\neq(u_{2},v_{2})\end{cases}.$

By organizing the conditions and combining equal values, the desired equation
can be obtained. ∎

######  Remark 5.1.

Using 5.1, we can also determine the average hitting times in the Cartesian
product of two distance-regular graphs by their intersection arrays. However,
as the number of parameters increases, the equation becomes more complex.
Therefore, it is not practical to represent the average hitting times by their
parameters in the Cartesian product of two typical distance-regular graphs. On
the other hand, it may be possible to provide the bounds of the average
hitting times in such a graph. The bounds of the average hitting times in a
distance-regular graph were given by Koolen and Markowsky [6], but in the
Cartesian product of two typical distance-regular graphs, such bounds are not
known.

##  6\. Average hitting time of generalized Paley graph in two specific cases

In this section, first we give a definition of a generalized Paley graph and
determine a function $f_{\alpha,k}$ such that a generalized Paley graph
becomes an $f_{\alpha,k}$-equitable graph. We also introduce the concept of a
class of graphs called quasi-strongly regular graphs and define the parameters
of a generalized Paley graph. Following this, we compute the quotient matrix
of two specific generalized Paley graph as $f_{\alpha,k}$-equitable graphs,
using only these parameters. We then proceed to calculate their average
hitting times.

### Definition of generalized Paley graph and some of its properties

Let $\mathbb{F}_{x}$ be a finite field with order $x$, and let
$\mathbb{F}_{x}^{*}$ be the multiplicative group of $\mathbb{F}_{x}$. Define
the $k$th power of $\mathbb{F}_{x}^{*}$ as
$(\mathbb{F}_{x}^{*})^{k}=\\{n^{k}\mid n\in\mathbb{F}_{x}^{*}\\}$.

######  Definition 6.1 (Generalized Paley graph [7]).

Let $x$ be a prime power, and let $k$ be an integer such that $x-1\equiv
1\pmod{2k}$. The generalized Paley graph, denoted as $GP(x,k)$, is defined
with the vertex set $\mathbb{F}_{x}$, and for any vertices $n$ and $m$ in
$GP(x,k)$, $n\sim m$ if $n-m\in(\mathbb{F}_{x}^{*})^{k}$.

Then, we obtain the following theorem.

######  Theorem 6.1.

Let $\alpha$ be the generator of $\mathbb{F}_{x}^{*}$, and let $f_{\alpha,k}$
be a function such that

$\displaystyle f_{\alpha,k}:\mathbb{F}_{x}\times\mathbb{F}_{x}$
$\displaystyle\mapsto\\{0,1,\ldots,k\\}$ $\displaystyle f_{\alpha,k}(u,v)$
$\displaystyle\mapsto\begin{cases}i&v-u\in\alpha^{i-1}(\mathbb{F}_{x}^{*})^{k}\\\
0&v-u=0\end{cases}.$

Then, $GP(x,k)$ is an $f_{\alpha,k}$-equitable graph.

###### Proof.

For any $l\in(\mathbb{F}_{x}^{*})^{k}$, we can consider an automorphism of
$\mathbb{F}_{x}$, denoted as $\tau_{l,\times}$, such that
$\tau_{l,\times}(n)=ln$. Since $(\mathbb{F}_{x}^{*})^{k}$ is a multiplicative
subgroup of $\mathbb{F}_{x}^{*}$, for any vertices $u$ and $v$ in $GP(x,k)$,

$\displaystyle u\sim v$ $\displaystyle\Longleftrightarrow
u-v\in(\mathbb{F}_{x}^{*})^{k}$
$\displaystyle\Longleftrightarrow\tau_{l,\times}(u-v)\in(\mathbb{F}_{x}^{*})^{k}$
$\displaystyle\Longleftrightarrow\tau_{l,\times}(u)\sim\tau_{l,\times}(v).$

Therefore, $\tau_{l,\times}$ is also an automorphism of $GP(x,k)$. Let

$\Pi=\\{\tau_{l,\times}\mid l\in(\mathbb{F}_{x}^{*})^{k}\\}$

be the automorphism set. Since $\tau_{l,\times}(0)=0$ for any
$l\in(\mathbb{F}_{x}^{*})^{k}$, $\tau_{l,\times}$ is a subset of the
stabilizer subgroup of vertex $0$. Define $P_{0}$ to be a partition based on
the orbits from $\Pi$. Then, we can denote $P_{0}$ as follows:

$P_{0}=\\{V_{0}=\\{0\\},V_{1}=(\mathbb{F}_{x}^{*})^{k},V_{2}=\alpha(\mathbb{F}_{x}^{*})^{k},V_{3}=\alpha^{2}(\mathbb{F}_{x}^{*})^{k},\ldots,V_{k}=\alpha^{k-1}(\mathbb{F}_{x}^{*})^{k}\\}.$

For any integers $i$ and $j$ such that $0\leq i,j\leq k$ and for any $v$ and
$v^{\prime}$ in $V_{i}$, there exists an automorphism $\tau_{\times,l}$ such
that $\tau_{\times,l}(v)=v^{\prime}$ and $\tau_{\times,l}(V_{j})=V_{j}$.
Therefore,

$|N(v)\cap
V_{j}|=|N(\tau_{\times,l}(v))\cap\tau_{\times,l}(V_{j})|=|N(v^{\prime})\cap
V_{j}|.$

This shows that $P_{0}$ is a stabilized equitable partition of $GP(x,k)$
centered on $0$. Here, let $F_{i}(n)=\\{v\in\mathbb{F}_{x}\mid
f_{\alpha,k}(n,v)=i\\}$, where $n$ is for any element of $\mathbb{F}_{x}$.
Then, from the definition of $f_{\alpha,k}$, we obtain that
$F_{i}(0)=\alpha^{i-1}(\mathbb{F}_{x}^{*})^{k}$. Therefore, we can also denote
$P_{0}$ by using $F_{i}(0)$ as follows:

$P_{0}=\\{F_{0}(0)=\\{0\\},F_{1}(0),\ldots,F_{k}(0)\\}.$

Next, we prove that

$P_{n}=\\{F_{0}(n)=\\{n\\},F_{1}(n),\ldots,F_{k}(n)\\}$

is a stabilized equitable partition of $GP(x,k)$ centered on $n$. Let
$\sigma_{n,+}$ be a permutation of $\mathbb{F}_{x}$ such that
$\sigma_{n,+}(a)=a+n$, where $n$ is for any element of $\mathbb{F}_{x}$. From
the definition of $GP(x,k)$, for any vertices $u$ and $v$ in $GP(x,k)$,

$\displaystyle u\sim v$ $\displaystyle\Longleftrightarrow
u-v\in(\mathbb{F}_{x}^{*})^{k}$
$\displaystyle\Longleftrightarrow\sigma_{n,+}(u)-\sigma_{n,+}(v)\in(\mathbb{F}_{x}^{*})^{k}$
$\displaystyle\Longleftrightarrow\sigma_{n,+}(u)\sim\sigma_{n,+}(v).$

Therefore, $\sigma_{n,+}$ is a graph automorphism of $GP(x,k)$. Since $P_{0}$
is an equitable partition,

$\sigma_{n,+}(P_{0})=\\{\sigma_{n,+}(F_{0}(0))=\\{n\\},\sigma_{n,+}(F_{1}(0)),\ldots,\sigma_{n,+}(F_{k}(0))\\}$

is also a stabilized equitable partition centered on $n$. Additionally,

$\displaystyle v\in F_{i}(0)$ $\displaystyle\Longleftrightarrow f(0,v)=i$
$\displaystyle\Longleftrightarrow f(n,n+v)=i$
$\displaystyle\Longleftrightarrow\sigma_{n,+}(v)\in F_{i}(n).$

Therefore,

$\sigma_{n,+}(P_{0})=\\{F_{0}(n),F_{1}(n),\ldots,F_{k}(n)\\}=P_{n}.$

Hence, for every vertex $n$, $P_{n}$ is a stabilized equitable partition of
$GP(x,k)$ centered on $n$. Finally, we check the condition of the quotient
matrix. Let the quotient matrix of $P_{n}$ be $q(n)_{ij}$. From the definition
of the quotient matrix,

$q(n)_{ij}=|N(v)\cap F_{i}(n)|,$

where $v\in F_{j}(n)$. Since $\sigma_{n,+}(F_{i}(0))=F_{i}(n)$, we obtain

$\displaystyle q(n)_{ij}$ $\displaystyle=|N(v)\cap F_{i}(n)|$
$\displaystyle=|N(\sigma_{n,+}(v-n))\cap\sigma_{n,+}(F_{i}(0))|$
$\displaystyle=|N(v-n)\cap F_{i}(0)|=q(0)_{ij}.$

This implies that the quotient matrix of $P_{n}$ does not depend on the choice
of $n$. Therefore, $GP(x,k)$ is an $f_{\alpha,k}$-equitable graph. ∎

The graph $GP(x,k)$ also belongs to the category of graphs known as quasi-
strongly regular.

######  Definition 6.2 (Quasi-strongly regular [4]).

Let $G$ be a $k$-regular graph with order $n$. $G$ is called quasi-strongly
regular with parameter $(n,k,c_{1};\\{c_{2},c_{3},\ldots,c_{l}\\})$ if $G$
satisfies the following for all pairs of vertices $u,v\in G$:

$|N(u)\cap N(v)|\in\begin{cases}\\{c_{1}\\}&u\sim v,\\\
\\{c_{2},c_{3},\ldots,c_{l}\\}&u\nsim v.\end{cases}$

When considering $GP(x,k)$, we can define $F_{i}(n)$ as the set
$\\{v\in\mathbb{F}_{x}\mid f_{\alpha,k}(n,v)=i\\}$ and create partitions for
each vertex $n$ as follows:

$\displaystyle P_{n}$
$\displaystyle=\\{F_{0}(n)=\\{n\\},F_{1}(n),\ldots,F_{k}(n)\\}.$

Since

$F_{1}(n)=\\{u\in V\mid u-n\in(\mathbb{F}_{x}^{*})^{k}\\}=N(n)$

and $GP(x,k)$ is $f_{\alpha,k}$-equitable, for every vertex $v$ in $N(n)$,
$|N(v)\cap N(n)|$ does not depend on the choice of vertex $v$. Therefore,
$GP(x,k)$ is quasi-strongly regular. Let $c_{i}=|N(0)\cap N(v)|$, where $v\in
F_{i}(0)$. Then, the parameters of $GP(x,k)$ as a quasi-strongly regular graph
are $(x,\frac{x-1}{k},c_{1};\\{c_{2},c_{3},\ldots,c_{k}\\})$.

### Some elements of quotient matrix of $GP(x,k)$ as $f_{\alpha,k}$-equitable
graph

From 1.1 and 6.1, it is sufficient to know the quotient matrix of $P_{0}$ to
compute the average hitting time of $GP(x,k)$. To compute it, we first
determine some elements of the quotient matrix of $P_{0}$ by the parameters of
$GP(x,k)$ as quasi-strongly regular. In the following, we denote
$P(x,k)=\\{F_{0},F_{1},\ldots,F_{k}\\}$ as the partition $P_{0}$ of $GP(x,k)$
and $q(x,k)_{ij}$ as the quotient matrix of $P_{0}$.

######  Lemma 6.1.

$\displaystyle q(x,k)_{0,i}$ $\displaystyle=\begin{cases}1&i=1\\\ 0&i\neq
1\end{cases}$ $\displaystyle q(x,k)_{i,0}$
$\displaystyle=\begin{cases}\frac{x-1}{k}&i=1\\\ 0&i\neq 1\end{cases}$
$\displaystyle q(x,k)_{1,i}$ $\displaystyle=c_{i}$

Additionally, for any integers $i,j$ such that $i,j\geq 1$,

$\displaystyle q_{ij}$ $\displaystyle=q_{ji}.$

###### Proof.

Because $N(0)=(\mathbb{F}_{x}^{*})^{k}=F_{1}$, we obtain
$q(x,k)_{0,1}=1,q(x,k)_{1,0}=\frac{x-1}{k}$ and for any integer $i$ such that
$2\leq i\leq k$, $q(x,k)_{0,i}=q(x,k)_{i,0}=0$. From the definition of
$c_{i}$, for any $1\leq i\leq k$,

$v\in F_{i}\Longrightarrow c_{i}=|N(0)\cap N(v)|=|F_{1}\cap
N(v)|=q(x,k)_{1,i}.$

From $|F_{1}|=|F_{2}|=\ldots=|F_{k}|=\frac{x-1}{k}$ and 2.2, we have

$q_{ij}=q_{ji}.$

∎

We can also determine $q(x,k)_{i,i}$.

######  Lemma 6.2.

$q(x,k)_{i,i}=c_{k-i+2}$

###### Proof.

From an algebraic perspective, $|N(v)\cap F_{i}|$ is the number of pairs of
solutions $(a_{1}^{k},\alpha^{i-1}a_{2}^{k})$ to the following polynomial with
coefficients in the finite field $\mathbb{F}_{x}$, neither of which is $0$:

$v-a_{1}^{k}=\alpha^{i-1}a_{2}^{k}.$

We denote $S(g(a_{1},a_{2},\ldots,a_{l}))$ as the number of sets of solutions
$(a_{1},a_{2},\ldots,a_{l})$ to equation $g(a_{1},a_{2},\ldots,a_{l})=0$, with
no $a_{i}$ equal to $0$. Then, when $v\in F_{j}$,

$\displaystyle q(x,k)_{ij}=|N(v)\cap F_{i}|$
$\displaystyle=\frac{|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-v)|}{k^{2}},$

so

$|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-v)|=k^{2}q(x,k)_{ij}.$

From this equation, we obtain that $|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-v)|$
does not depend on the choice of $v\in F_{j}$. Here, for any $v\in F_{j}$,
there exists $m\in\mathbb{F}_{x}^{*}$ such that $v=\alpha^{j-1}m^{k}$.
Therefore,

$\displaystyle|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{j-1}a_{3}^{k})|$
$\displaystyle=\sum_{m=1}^{x-1}|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{j-1}m^{k})|$
$\displaystyle=(x-1)|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-v)|$ (3)
$\displaystyle=(x-1)k^{2}q(x,k)_{ij}.$

From 6.1, if $j=1$ then

(4) $|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-a_{3}^{k})|=(x-1)k^{2}c_{i}.$

Here,

$\displaystyle
a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{j-1}a_{3}^{k}=0\Longleftrightarrow\alpha^{l}a_{1}^{k}+\alpha^{i-1+l}a_{2}^{k}-\alpha^{j-1+l}a_{3}^{k}=0.$

Therefore,

(5)
$|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{j-1}a_{3}^{k})|=|S(\alpha^{l}a_{1}^{k}+\alpha^{i-1+l}a_{2}^{k}-\alpha^{j-1+l}a_{3}^{k})|.$

From Sections 6, 4 and 5,

$\displaystyle(x-1)k^{2}q(x,k)_{i,i}$
$\displaystyle=|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{i-1}a_{3}^{k})|$
$\displaystyle=|S(\alpha^{k-(i-1)}a_{1}^{k}+\alpha^{k}a_{2}^{k}-\alpha^{k}a_{3}^{k})|$
$\displaystyle=|S(\alpha^{k-(i-1)}a_{1}^{k}+a_{2}^{k}-a_{3}^{k})|$
$\displaystyle=|S(a_{1}^{k}+\alpha^{k-(i-1)}a_{2}^{k}-a_{3}^{k})|$
$\displaystyle=(x-1)k^{2}c_{k-i+2}.$

Hence,

$q(x,k)_{i,i}=c_{k-i+2}.$

∎

Especially, we can compute all of the entries of $q(x,3)_{ij}$ and
$q(x,4)_{ij}$ from their parameters.

### Average hitting time of $GP(x,3)$

In this subsection, we compute the average hitting time of $GP(x,3)$ by its
parameter as a quasi-strongly regular graph.

######  Theorem 6.2.

Let $\alpha$ be the generator of $\mathbb{F}_{x}^{*}$, and let
$c_{i}=|N(v)\cap N(u)|$, where $u-v\in\alpha^{i-1}(\mathbb{F}_{x}^{*})^{3}$
and $i$ is for any integer such that $1\leq i\leq 3$.

$H(GP(x,3);(v,u))=\begin{cases}0&u-v=0\\\
x-1&u-v\in(\mathbb{F}_{x}^{*})^{3}\\\
\frac{\frac{x-1}{3}(c_{1}(3c_{2}+3c_{3}+2)+3c_{2}(c_{3}+1)+4c_{3}+2)}{c_{2}(c_{1}+c_{3}+1)+(c_{1}+1)c_{3}}&u-v\in\alpha(\mathbb{F}_{x}^{*})^{k}\\\
\frac{\frac{x-1}{3}(c_{1}(3c_{2}+3c_{3}+2)+c_{2}(3c_{3}+4)+3c_{3}+2)}{c_{2}(c_{1}+c_{3}+1)+(c_{1}+1)c_{3}}&u-v\in\alpha^{2}(\mathbb{F}_{x}^{*})^{k}\end{cases}$

###### Proof.

From 6.1 and 6.2, there are only two entries that have not been computed,
namely, $q(x,3)_{2,3}$ and $q(x,3)_{3,2}$. However, from 2.1 and the fact that
the valency of $GP(x,3)$ is $\frac{x-1}{3}$,

$\sum_{i=0}^{3}q(x,3)_{i,2}=\sum_{i=0}^{3}q(x,3)_{i,3}=\sum_{i=0}^{3}q(x,1)_{i,3}=1+c_{1}+c_{2}+c_{3}.$

Therefore,

$q(x,3)_{ij}=\begin{pmatrix}0&1&0&0\\\ \frac{x-1}{3}&c_{1}&c_{2}&c_{3}\\\
0&c_{2}&c_{3}&1+c_{1}\\\ 0&c_{3}&1+c_{1}&c_{2}\end{pmatrix}.$

From 6.1, $GP(x,3)$ is an $f_{\alpha,3}$-equitable graph. We define
$(h_{1},h_{2},h_{3})$ as follows:

$\displaystyle(h_{1},h_{2},h_{3})$ $\displaystyle=\vec{H}(q(x,3)_{ij})$
$\displaystyle=\begin{pmatrix}x-1\\\
\frac{\frac{x-1}{3}(c_{1}(3c_{2}+3c_{3}+2)+3c_{2}(c_{3}+1)+4c_{3}+2)}{c_{2}(c_{1}+c_{3}+1)+(c_{1}+1)c_{3}}\\\
\frac{\frac{x-1}{3}(c_{1}(3c_{2}+3c_{3}+2)+c_{2}(3c_{3}+4)+3c_{3}+2)}{c_{2}(c_{1}+c_{3}+1)+(c_{1}+1)c_{3}}\end{pmatrix}^{\top}.$

From 1.1, since $GP(x,3)$ is $f_{\alpha,3}$-equitable,

$\displaystyle H(GP(x,3);(v,u))$ $\displaystyle=\begin{cases}0&u=v\\\
h_{f_{\alpha,k}(u,v)}&u\neq v\end{cases}.$

By organizing the conditions, the desired equation can be obtained. ∎

### Average hitting time of $GP(x,4)$

In this subsection, we compute the average hitting time of $GP(x,3)$ by its
parameter as a quasi-strongly regular graph.

######  Theorem 6.3.

Let $\alpha$ be the generator of $\mathbb{F}_{x}^{*}$, let $c_{i}=|N(v)\cap
N(u)|$, where $u-v\in\alpha^{i-1}(\mathbb{F}_{x}^{*})^{4}$ and, for any
integer $i$ such that $1\leq i\leq 4$, define $h_{i}$ as follows:

$\displaystyle h_{1}$ $\displaystyle=x-1$ $\displaystyle h_{2}$
$\displaystyle=\frac{(x-1)\left(\begin{array}[]{c}1280c_{3}^{3}-64c_{3}^{2}(8c_{4}+7x-13)\\\
+4c_{3}\left(64c_{4}^{2}+32c_{4}(x-2)+9x^{2}-48x+39\right)\\\
-(x-1)\left(64c_{4}^{2}-24c_{4}-9x+9\right)\end{array}\right)}{64\left(\begin{array}[]{c}20c_{3}^{3}+c_{3}^{2}(-8c_{4}-7x+7)+4c_{3}c_{4}^{2}\\\
+2c_{3}c_{4}(x-1)+\frac{9}{16}c_{3}(x-1)^{2}-c_{4}^{2}(x-1)\end{array}\right)}$
$\displaystyle h_{3}$
$\displaystyle=\frac{(x-1)\left(\begin{array}[]{c}1280c_{3}^{3}-64c_{3}^{2}(8c_{4}+7x-10)\\\
+4c_{3}\left(64c_{4}^{2}+32c_{4}x+9x^{2}-42x+33\right)\\\
-2\left(32c_{4}^{2}+9\right)x+9x^{2}+9\end{array}\right)}{64\left(\begin{array}[]{c}20c_{3}^{3}+c_{3}^{2}(-8c_{4}-7x+7)+4c_{3}c_{4}^{2}\\\
+2c_{3}c_{4}(x-1)+\frac{9}{16}c_{3}(x-1)^{2}-c_{4}^{2}(x-1)\end{array}\right)}$
$\displaystyle h_{4}$
$\displaystyle=\frac{(x-1)\left(\begin{array}[]{c}1280c_{3}^{3}-64c_{3}^{2}(8c_{4}+7x-9)\\\
+4c_{3}\left(64c_{4}^{2}+32c_{4}x+9\left(x^{2}-4x+3\right)\right)\\\
-(x-1)\left(64c_{4}^{2}+24c_{4}-9x+9\right)\end{array}\right)}{64\left(\begin{array}[]{c}20c_{3}^{3}+c_{3}^{2}(-8c_{4}-7x+7)+4c_{3}c_{4}^{2}\\\
+2c_{3}c_{4}(x-1)+\frac{9}{16}c_{3}(x-1)^{2}-c_{4}^{2}(x-1)\end{array}\right)}.$

Then,

$H(GP(x,4);(v,u))=\begin{cases}0&u-v=0\\\
h_{1}&u-v\in(\mathbb{F}_{x}^{*})^{4}\\\
h_{2}&u-v\in\alpha(\mathbb{F}_{x}^{*})^{4}\\\
h_{3}&u-v\in\alpha^{2}(\mathbb{F}_{x}^{*})^{4}\\\
h_{4}&u-v\in\alpha^{3}(\mathbb{F}_{x}^{*})^{4}\\\ \end{cases}.$

To prove 6.3, we should know all the entries of $Q(x,4)$. Therefore, we prove
the following lemma.

######  Lemma 6.3.

$Q(x,4)=\begin{pmatrix}0&1&0&0&0\\\ \frac{x-1}{4}&c_{1}&c_{2}&c_{3}&c_{4}\\\
0&c_{2}&c_{4}&\frac{1+c_{1}+c_{3}}{2}&\frac{1+c_{1}+c_{3}}{2}\\\
0&c_{3}&\frac{1+c_{1}+c_{3}}{2}&c_{3}&\frac{1+c_{1}+c_{3}}{2}\\\
0&c_{4}&\frac{1+c_{1}+c_{3}}{2}&\frac{1+c_{1}+c_{3}}{2}&c_{2}\end{pmatrix}$

###### Proof.

$x-1\equiv 0\pmod{2k}$, $-1$ is in $(\mathbb{F}_{x}^{*})^{k}$ and there exists
the element $\beta$ in $\mathbb{F}_{x}$ such that $\beta^{k}=-1$. Then,

$a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{j-1}a_{3}^{k}=0\Longleftrightarrow-(\beta
a_{1})^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{j-1}a_{3}^{k}=0.$

Therefore, we obtain

$|S(a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{j-1}a_{3}^{k})|=|S(-a_{1}^{k}+\alpha^{i-1}a_{2}^{k}-\alpha^{j-1}a_{3}^{k})|.$

Similar reasoning can be applied to the coefficients of $a_{2}$ and $a_{3}$ as
well. Hence, the signs of the terms in $xa_{1}^{k}+ya_{2}^{k}+za_{3}^{k}$ do
not affect $|S(xa_{1}^{k}+ya_{2}^{k}+za_{3}^{k})|$. In the case $k=4$, from
Sections 6 and 5,

$\displaystyle(x-1)4^{2}q(x,4)_{4,2}$ $\displaystyle=|S(a_{1}^{4}+\alpha
a_{2}^{4}-\alpha^{3}a_{3}^{4})|$ $\displaystyle=|S(\alpha
a_{1}^{4}+\alpha^{2}a_{2}^{4}-(\alpha a_{3})^{4})|$
$\displaystyle=|S(a_{1}^{4}+\alpha
a_{2}^{4}-\alpha^{2}a_{3}^{4})|=(x-1)4^{2}q(x,4)_{3,2}.$

Therefore, $q(x,4)_{3,2}=q(x,4)_{4,2}$. From 2.1,

$\sum_{i=0}^{4}q(x,4)_{i,2}=c_{2}+c_{4}+q(x,4)_{3,2}+q(x,4)_{4,2}=1+c_{1}+c_{2}+c_{3}+c_{4}.$

Hence, $q(x,4)_{3,2}=q(x,4)_{4,2}=\frac{1+c_{1}+c_{3}}{2}$. From 6.1 and 6.2,
we can compute the remaining entries:

$Q(x,4)=\begin{pmatrix}0&1&0&0&0\\\ \frac{x-1}{k}&c_{1}&c_{2}&c_{3}&c_{4}\\\
0&c_{2}&c_{4}&\frac{1+c_{1}+c_{3}}{2}&\frac{1+c_{1}+c_{3}}{2}\\\
0&c_{3}&\frac{1+c_{1}+c_{3}}{2}&c_{3}&\frac{1+c_{1}+c_{3}}{2}\\\
0&c_{4}&\frac{1+c_{1}+c_{3}}{2}&\frac{1+c_{1}+c_{3}}{2}&c_{2}\end{pmatrix}.$

∎

Because the column sums of $Q(x,4)$ are always $\frac{x-1}{4}$, there are non-
trivial constraints on the parameters.

######  Corollary 6.1.

$c_{2}+c_{4}=2c_{3}.$

###### Proof.

$\displaystyle\sum_{i=0}^{r}q(x,4)_{i,1}$
$\displaystyle=\sum_{i=0}^{r}q(x,4)_{i,3}$ $\displaystyle\Longleftrightarrow
1+c_{1}+c_{2}+c_{3}+c_{4}$ $\displaystyle=1+c_{1}+3c_{3}$
$\displaystyle\Longleftrightarrow c_{2}+c_{4}$ $\displaystyle=2c_{3}.$

∎

Next, we give a proof of 6.3.

###### Proof of 6.3.

From 6.1 and 6.3, $GP(x,4)$ is $f$-equitable with the following quotient
matrix $q(x,4)_{ij}$:

$q(x,4)_{ij}=\begin{pmatrix}0&1&0&0&0\\\
\frac{x-1}{k}&c_{1}&c_{2}&c_{3}&c_{4}\\\
0&c_{2}&c_{4}&\frac{1+c_{1}+c_{3}}{2}&\frac{1+c_{1}+c_{3}}{2}\\\
0&c_{3}&\frac{1+c_{1}+c_{3}}{2}&c_{3}&\frac{1+c_{1}+c_{3}}{2}\\\
0&c_{4}&\frac{1+c_{1}+c_{3}}{2}&\frac{1+c_{1}+c_{3}}{2}&c_{2}\end{pmatrix}.$

By computing $\vec{H}(q(x,4)_{ij})$, we have

$\displaystyle(h_{1},h_{2},h_{3},h_{4})=\vec{H}(q(x,4)_{ij}).$

From 1.1, because $GP(x,4)$ is $f_{\alpha,4}$-equitable,

$\displaystyle H(G;\\{u,v\\})$ $\displaystyle=\begin{cases}0&u=v\\\
h_{f(u,v)}&u\neq v\end{cases}$ $\displaystyle=\begin{cases}0&u-v=0\\\
h_{1}&u-v\in(\mathbb{F}_{x}^{*})^{4}\\\
h_{2}&u-v\in\alpha(\mathbb{F}_{x}^{*})^{4}\\\
h_{3}&u-v\in\alpha^{2}(\mathbb{F}_{x}^{*})^{4}\\\
h_{4}&u-v\in\alpha^{3}(\mathbb{F}_{x}^{*})^{4}\\\ \end{cases}.$

∎

######  Remark 6.1.

We determined $P(x,4)$ and obtained 6.1 as a side effect. From an algebraic
perspective, the parameters of $GP(x,k)$ as a quasi-strongly regular graph can
be calculated using the Jacobi sum, which is a type of character sum.
Therefore, we may obtain relational equations for some other $k$ similar to
6.1 using the properties of the Jacobi sum. If such equations are found for
some other $k$, we may calculate $P(x,k)$ using only the parameters of
$GP(x,k)$ as a quasi-strongly regular graph, and also determine the average
hitting times in $GP(x,k)$.

######  Remark 6.2.

We proved that $G$ is a distance-regular graph if and only if $G$ is a
$d_{G}$-equitable graph. We also claimed that the Cartesian product of two
strongly regular graphs, denoted as $G_{1}$ and $G_{2}$, is a
$(d_{G_{1}},d_{G_{2}})$-equitable graph and $GP(x,k)$ is an
$f_{\alpha,k}$-equitable graph. In these cases, $(d_{G_{1}},d_{G_{2}})$ and
$f_{\alpha,k}$ are “limited” functions, which means that they can be defined
for only specific graphs. On the other hand, the function $d_{G}$ can be
defined for any graph. We consider that if a function $f$ can be considered on
general graphs, then $f$-equitable graphs may have some properties similar to
distance-regular graphs, such as the bounds of the average hitting times,
which is the result of Koolen and Markowsky [6].

To give an example of such a function, we can consider the function
$n_{G}(u,v)$ that represents the number of common neighbors of two vertices
$u$ and $v$ in graph $G$. We define $G$ as being neighbor-equitable if $G$ is
an $n_{G}$-equitable graph. The simplest example of neighbor-equitable is a
strongly regular graph with parameters $(n,d,a,c)$, where $d,a$ and $c$ are
all distinct integers. From this, although there are some constraints on the
parameters, neighbor-equitable graphs can also be considered as a
generalization of strongly regular graphs.

Let the parameters of $GP(x,k)$ as quasi-strongly regular be
$(x,\frac{x-1}{k},c_{1};c_{2},\ldots,c_{k})$. In fact, when
$c_{1},c_{2},\ldots,c_{k}$ are all distinct integers, then $GP(x,k)$ is also
neighbor-equitable. This is because $F_{i}(n)=N_{c_{i}}(n)$ holds for all
integers $i$ and $n$ such that $0\leq i\leq k$ and $n\in\mathbb{F}_{x}$, where
$N_{c_{i}}(n)=\\{v\in GP(x,k)\mid|N(n)\cap N(v)|=c_{i}\\}$. It is not known
what other types of neighbor-equitable graphs may exist.

## Acknowledgments

The author thanks Professors Tsuyoshi Miezaki, Akihiro Munemasa, and Hiroshi
Suzuki and Ph.D. student Yuuho Tanaka for their helpful discussions and
comments.

## References

  * [1] N.L. Biggs.  Potential theory on distance-regular graphs.  Combinatorics, Probability and Computing, 2(3):243–255, 1993.
  * [2] A.E. Brouwer, A.M. Cohen, and A. Neumaier.  Distance-Regular Graphs.  Springer Berlin, Heidelberg, 1989.
  * [3] L. Devroye and A. Sbihi.  Random walks on highly symmetric graphs.  Journal of Theoretical Probability, 3(4):497–514, Oct 1990.
  * [4] W.L. Golightly, W.H. Haynsworth, and D.G. Sarvate.  A family of connected quasi-strongly regular graphs.  Congressus Numerantium, pages 89–96, 1997.
  * [5] Wolfram Research, Inc.  Mathematica, Version 12.3.  Champaign, IL, 2021.
  * [6] J.H. Koolen and G. Markowsky.  A collection of results concerning electric resistance and simple random walk on distance-regular graphs.  Discrete Mathematics, 339(2):737–744, 2016.
  * [7] T.K. Lim and C.E. Praeger.  On generalised Paley graphs and their automorphism groups.  Michigan Mathematical Journal, 58(1):293 – 308, 2009.
  * [8] A.J. Schwenk.  Computing the characteristic polynomial of a graph.  In Ruth A. Bari and Frank Harary, editors, Graphs and Combinatorics, pages 153–172, Berlin, Heidelberg, 1974. Springer Berlin Heidelberg.
  * [9] A.R.D. Van Slijpe.  Random walks on regular polyhedra and other distance-regular graphs.  Statistica Neerlandica, 38(4):273–292, 1984.


# Superconductivity of Light-Elements Doped H3S

Hongyi Guan  Ying Sun  International Center for Computational Method $\&$
Software and State Key Laboratory of Superhard materials, College of Physics,
Jilin University, Changchun 130012, China  Hanyu Liu<EMAIL_ADDRESS>International Center for Computational Method $\&$ Software and State Key
Laboratory of Superhard materials, College of Physics, Jilin University,
Changchun 130012, China  Key Laboratory of Physics and Technology for Advanced
Batteries (Ministry of Education), College of Physics, Jilin University,
Changchun 130012, China  International Center of Future Science, Jilin
University, Changchun 130012, China

###### Abstract

Pressurized hydrogen-rich compounds, which could be viewed as precompressed
metallic hydrogen, exhibit high superconductivity, thereby providing a viable
route toward the discovery of high-temperature superconductors. Of particular
interest is to search for high-temperature superconductors with low stable
pressure in terms of pressure-stabilized hydrides. In this work, with the aim
of obtaining high-temperature superconducting compounds at low pressure, we
attempt to study the doping effects for high-temperature superconductive
$\mathrm{H_{3}S}$ with supercells up to 64 atoms using first principle
electronic structure simulations. As a result of various doping, we found that
Na doping for $\mathrm{H_{3}S}$ could lower the dynamically stable pressure by
40 GPa. The results also indicate P doping could enhance the superconductivity
of $\mathrm{H_{3}S}$ system, which is in agreement with previous calculations.
Moreover, our work proposed an approach that could reasonably estimate the
superconducting critical temperature ($T_{c}$) of a compound containing a
large number of atoms, saving the computational cost significantly for large-
scale elements-doping superconductivity simulations.

††preprint: APS/123-QED

##  I INTRODUCTION

The search for the high-temperature superconducting hydrides at high pressures
has attracted attention in condensed matter physics field. In this regard,
many hydrides with relatively high $T_{c}$ were identified under high pressure
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]. Among these high-
temperature superconducting hydrides, the theoretically predicted
$\mathrm{H_{3}S}$ with $T_{c}$ of 203 K [1, 2, 3] and $\mathrm{LaH_{10}}$ with
$T_{c}$ of 250-260 K in [5, 6, 8, 7], as well as CaH6 being the first example
of clathrate hydrides ever predicted [16, 17, 18], were experimentally
synthesized. Recently, the carbonaceous sulfur hydride was found to possess
extremely high superconductivity with a $T_{c}$ as high as 288 K at 267 GPa
[12], however, the actual crystal structure and the mechanisms of such
extremely high superconductivity remains unclear and missing [19, 20, 21, 22,
23].

Structure searches below 200 GPa were performed for the C-S-H system [21, 19,
20, 24, 25], while no high superconductive structure is yet identified. Later,
it was reported that the high superconductivity in the C-S-H compound could be
explained by the doping of C into the $Im\bar{3}m$ $\mathrm{H_{3}S}$ [26, 21],
whereas these simulations are based on the virtual crystal approximation (VCA)
[27]. This approximation is employed with linearly mixed pseudopotentials and
couldnot take the details of symmetry breaking and local distortions into
account. These issues, in principle, could be addressed by performing the
electronic simulations of doping carbon into a sufficiently large supercell of
$\mathrm{H_{3}S}$, if the computational power is allowed.

In this paper, we investigated the structures and physical properties of
partially substituting sulfur by the light elements in $Im\bar{3}m$
$\mathrm{H_{3}S}$ with supercell approach at the pressure range of 150-250 GPa
by first-principle calculations. Our calculations mainly focus on
$\mathrm{H_{24}S_{7}X}$ and $\mathrm{H_{48}S_{15}X}$, where $\mathrm{X}$
denotes the doping elements from H to Cl without He and Ne in the periodic
table. As a result, we found that the Na doing could lower the dynamically
stable pressure of 40 GPa compared to the parent $\mathrm{H_{3}S}$ system.
Furthermore, the P doping could enhance the superconductivity of the parent
$\mathrm{H_{3}S}$ system, which is ascribed to octahedra units [SH6] and
[PH6]. In addition, we proposed an estimation approach to investigate the low
proportion C-doping effects at 260 GPa. The results suggest the estimated
$T_{c}$ is much lower than the room temperature.

##  II COMPUTATIONAL DETAILS

The structural optimization was done by the Vienna Ab initio Simulation
Package (VASP) [28], with pseudopotentials employing generalized gradient
approximation (GGA) based Perdew-Burke-Ernzerhof (PBE) type exchange
correlation functional [29] and projector-augmented wave method [30].
Monkhorst $\bm{k}$ meshes [31] spacing $2\pi\times 0.1$ Å-1 was used to sample
the first Brillouin Zones. The electronic density of states was also computed
by VASP with $20\times 20\times 20$ $\bm{k}$ mesh and was analyzed by VASPKIT
[32]. The phonon properties and superconducting properties were computed by
the Quantum-Espresso (QE) package, with vanderbilt ultra-soft pseudopotentials
[33]. We have adopted $\bm{k}$ mesh of $16\times 16\times 16$ and $\bm{q}$
mesh of $4\times 4\times 4$ and tested the convergence with $\bm{k}$ mesh of
$20\times 20\times 20$ and $\bm{q}$ mesh of $5\times 5\times 5$ for
$\mathrm{H_{24}S_{7}X}$. For $\mathrm{H_{48}S_{15}X}$, $\bm{k}$ mesh was used
as $12\times 12\times 12$ and $\bm{q}$ mesh was used as $3\times 3\times 3$.
The smearing method was Methfessel-Paxton first-order spreading [34] of 0.03
Ry. The cutoff energy for basis of plane waves was employed to be 100 Ry.
Then, the transition temperatures were estimated by McMillan-Allen-Dynes (MAD)
formula [35]

$T_{c}=f_{1}f_{2}\dfrac{\omega_{\mathrm{log}}}{1.20}\mathrm{exp}\left[-\dfrac{1.04(1+\lambda)}{\lambda-\mu^{*}(1+0.62\lambda)}\right]$
(1)

where

$\displaystyle f_{1}$
$\displaystyle=\left\\{1+\left[\dfrac{\lambda}{2.46(1+3.8\mu^{*})}\right]^{3/2}\right\\}^{1/3}$
(2) $\displaystyle f_{2}$
$\displaystyle=1+\dfrac{\lambda^{2}(\omega_{2}/\omega_{\text{log}}-1)}{\lambda^{2}+[1.82(1+6.3\mu^{*})(\omega_{2}/\omega_{\text{log}})]^{2}}$

are the correction factors. $\mu^{*}$, $\lambda$ and $\omega_{\text{log}}$
indicate the screened Coulomb parameter, electron-phonon coupling constant and
the logarithm average over phonon frequency, respectively.

We have also computed the results by Migdal-Eliashberg (ME) theory [36, 37,
38, 39]

$\displaystyle Z(i\omega_{j})=1+\dfrac{\pi
T}{\omega_{j}}\sum\limits_{j^{\prime}}\dfrac{\omega_{j^{\prime}}}{\sqrt{\omega_{j^{\prime}}^{2}+\Delta^{2}(i\omega_{j^{\prime}})}}\lambda(i\omega_{j}-i\omega_{j^{\prime}})$
(3) $\displaystyle\begin{aligned} Z(i\omega_{j})\Delta(i\omega_{j})&=\pi
T\sum\limits_{j^{\prime}}\dfrac{\Delta(i\omega_{j^{\prime}})}{\sqrt{\omega_{j^{\prime}}^{2}+\Delta^{2}(i\omega_{j^{\prime}})}}\\\
&\times[\lambda(i\omega_{j}-i\omega_{j^{\prime}})-\mu^{*}]\end{aligned}$ (4)
$\displaystyle\lambda(i\omega_{j}-i\omega_{j^{\prime}})=\int\mathrm{d}\omega\dfrac{2\omega\alpha^{2}F(\omega)}{\omega^{2}+(\omega_{j}-\omega_{j^{\prime}})^{2}}$
(5)

to compare with that of MAD equation, which is realized by the Elk code [40].
$T_{c}$ could be obtained once the superconducting gap $\Delta(i\omega_{j})$
becomes zero in numerically solving ME equation.

Figure 1: Summary of dynamical stability and stable pressure ranges of
$\mathrm{H_{24}S_{7}X}$, where X is the dopant.

##  III RESULTS AND DISCUSSIONS

We began our simulations on investigating the validity of the supercell
approach by computing the electronic properties and phonon properties of
primitive cell and a supercell of 32 atoms ($\mathrm{H_{24}S_{8}}$) for
$\mathrm{H_{3}S}$ at 200 GPa, as shown in Fig. S1 [41]. As shown in Fig. S2
[41], the superconductivity using the supercell is well consistent with that
simulated from primitive cell of $\mathrm{H_{3}S}$, which is also in agreement
with previous results [2, 3]. The relevant information is listed in Table S1
[41].

Figure 2: Phonon dispersion and phonon linewidth for $\mathrm{H_{24}S_{7}Na}$
at pressure (a) 150 GPa, (b) 200 GPa and (c) 250 GPa, the magnitude of the
phonon linewidth is indicated by the radii of blue circles. (d) Phonon density
of states for $\mathrm{H_{24}S_{7}Na}$ at 150-250 GPa. Figure 3: (a)
Electronic band structure (left panel) and projected density of states (right
panel) of $\mathrm{H_{48}S_{15}P}$ at 200 GPa. (b) Phonon dispersion with
phonon linewidth (left panel) and phonon density of states (right panel) of
$\mathrm{H_{48}S_{15}P}$ at 200 GPa. The radii of the blue circles indicate
the magnitude of the phonon linewidth. (c) Atom projected and orbital
projected band structures (left panel) and density of states (right panel) of
$\mathrm{H_{48}S_{15}P}$ at 200 GPa near the Fermi surface. The width of the
lines indicates the weights of the corresponding orbitals. Due to the low
proportion of P atoms, their weights are displayed fivefold. (d) Crystal
structure of $\mathrm{H_{48}S_{15}P}$ at 200 GPa. The structures of
[$\mathrm{PH_{6}}$] and [$\mathrm{SH_{6}}$] units are represented by the
purple and yellow octahedra units respectively.

Furthermore, we have systematically investigated the doping of
$\mathrm{H_{3}S}$ by the elements from H to Cl without He and Ne in the
periodic table using supercells of 32 and 64 atoms. The structures of
$\mathrm{H_{24}S_{7}X}$ and $\mathrm{H_{48}S_{15}X}$ are provided in Fig. S3
[41]. The results indicate the doping could destabilize the structure for
several compounds. For the $\mathrm{H_{24}S_{7}X}$ compounds, for example,
imaginary frequency was found for $\Gamma$ point with X=H, indicating
dynamical instability. The dynamical stability of $\mathrm{H_{24}S_{7}X}$
compounds within the range of 150-250 GPa is summarized in Fig. 1. Moreover,
we found that 12.5% doping of Na into $\mathrm{H_{3}S}$ has a lower dynamical
stable pressure (140 GPa) compared to 180 GPa of the parent $\mathrm{H_{3}S}$
[2]. The absence of imaginary phonon frequency in the simulated phonon
dispersion implies the dynamical stability of $\mathrm{H_{24}S_{7}Na}$, as
shown in Fig. 2. It is clearly seen that the strongest electron-phonon
interaction mainly emerges around $P$ point, which may lead to a large
$\lambda$ of 2.31. As a result, $T_{c}$ of $\mathrm{H_{24}S_{7}Na}$ can reach
191 K at 150 GPa by using ME equation with $\mu^{*}=0.10$.

Figure 4: Calculated $x$ dependence of $T_{c}$ for H3S1-xCx at 260 GPa. The points in the gray region are estimated by Eqs. (6), (7). Table 1: The parameters of the superconductivity for the doped $\mathrm{H_{3}S}$ at a pressure range of 150-250 GPa, where the typical screened Coulomb parameter $\mu^{*}$ of 0.1-0.13 is employed. Dopant | Doping ratio | Pressure (GPa) | $\lambda$ |  $\omega_{\mathrm{log}}$ (K) |  $N(0)$ (States/Ry/atom) |  $T_{c}$ by MAD equation (K) |  $T_{c}$ by ME equation (K)
---|---|---|---|---|---|---|---
B | 0.1250 | 200 | 1.56 | 1281 | 0.721 | 154-171 | 176-191
B | 0.1250 | 250 | 1.21 | 1447 | 0.692 | 126-143 | 140-156
C | 0.1250 | 250 | 1.40 | 1259 | 0.709 | 134-150 | 153-169
F | 0.1250 | 250 | 1.04 | 1428 | 0.605 | 97-113 | 105-120
Na | 0.1250 | 150 | 2.31 | 846 | 0.656 | 154-169 | 178-191
Na | 0.1250 | 200 | 1.56 | 1094 | 0.660 | 133-148 | 149-167
Na | 0.1250 | 250 | 1.42 | 1152 | 0.667 | 125-140 | 138-152
Si | 0.1250 | 200 | 1.99 | 1155 | 0.838 | 182-199 | 210-225
Si | 0.1250 | 250 | 1.59 | 1294 | 0.849 | 161-179 | 188-205
P | 0.1250 | 200 | 2.02 | 1238 | 0.841 | 197-215 | 222-238
P | 0.1250 | 250 | 1.53 | 1520 | 0.922 | 180-199 | 207-224
P | 0.0625 | 200 | 2.29 | 1193 | 0.933 | 212-231 | 246-262
P | 0.0625 | 250 | 1.66 | 1512 | 0.955 | 196-216 | 227-244
Cl | 0.1250 | 200 | 1.31 | 1424 | 0.706 | 137-154 | 153-168
Cl | 0.1250 | 250 | 1.08 | 1591 | 0.700 | 115-133 | 129-145
S | - | 200 | 1.85 | 1358 | 0.868 | 195-214 | 222-238
S | - | 250 | 1.46 | 1571 | 0.875 | 175-195 | 197-219

As shown in previous studies [42, 43], the P doped $\mathrm{H_{3}S}$ has the
high superconductivity due to the enhanced density of states at the Fermi
level of parent $\mathrm{H_{3}S}$. We have also performed the simulations for
elucidating the physical mechanism of this compound by using a supercell of 64
atoms ($\mathrm{H_{48}S_{15}P}$). As is shown in Fig. 3(a) and Fig. S4, there
are several flat bands along the $\bm{k}$ path $F\to Q\to Z$ at the Fermi
surface, with the derivative $\partial E_{n}/\partial k$ almost zero. This
indicates that the doping of P alters the two van Hove singularities [44, 42]
and can result in a peak of density of states right at the Fermi surface.
Moreover, we found that the symmetry is preserved well after doping due to the
existence of the near degeneracies in electronic band structures as shown in
Fig. 3(a), which can also be a critical factor to induce Van Hove
singularities [23]. The high electronic density of states at the Fermi level
could contribute to the large magnitude of phonon linewidth, as shown in Fig.
3(b) and contrasted with Fig. S5 [41]. We have also found the hybridization of
$s$ orbitals of H with $p$ orbitals of S and P near the Fermi surface (Fig.
3(c)). The negligible curvature of the flat bands indicates well localization
of corresponding $s$ and $p$ electrons, revealing the strong P-H and S-H
chemical bondings. Fig. 3(d) shows the existence of [$\mathrm{PH_{6}}$] and
[$\mathrm{SH_{6}}$] units, where the distances between P-H and S-H are
compressed to 1.470 Å and 1.474 Å, compared with 1.493 Å in $\mathrm{H_{3}S}$
and 1.494 Å-1.511 Å for other S-H bonds in $\mathrm{H_{48}S_{15}P}$. Finally,
we found that the 6.25% P doping could enhance the $T_{c}$ of
$\mathrm{H_{3}S}$ around 20-30 K at 200 GPa and 250 GPa.

To explore the superconductivity of the C-doped $\mathrm{H_{3}S}$, we have
computed the electron-phonon coupling strength of $\mathrm{H_{32}S_{7}C}$,
$\mathrm{H_{36}S_{11}C}$ and $\mathrm{H_{48}S_{15}C}$. For larger supercells
corresponding to lower-proportion C-doped $\mathrm{H_{3}S}$, the simulations
could not be afforded due to computational demanding of these simulations as
well as the limition of our computational power. Therefore, we attempt to
estimate the superconductivity of low-proportion C-doped $\mathrm{H_{3}S}$
without performing actual electron-phonon coupling simulations for a large
supercell. Given that similar structures of the low-proportion C-doped
$\mathrm{H_{3}S}$ shares similar magnitude of average mass and electron-phonon
interaction at the same pressure, we could thus estimate $\lambda$ of the
$\mathrm{MgB_{2}}$ type superconductors by the Hopfield expression [45, 46]

$\lambda=\dfrac{N(0)I^{2}}{M\omega^{2}}$ (6)

Then, the $T_{c}$ can be estimated by [46]

$T_{c}=\omega\exp\left(-\dfrac{1}{\frac{\lambda}{1+\lambda}-\mu^{*}}\right)$
(7)

Further details of our estimation approach is also provided in the
supplemental material [41]. As is shown in Table S2, values of $T_{c}$
computed from our approach vary only about 5% at maximum compared with that
directly computed by QE, indicating the validity of our computational scheme.
We thus investigated the superconductivity of the doping system of H3S up to
256 atoms as shown in Table S3 and Fig. 4. The $T_{c}$ of H3S1-xCx with
$x$=0.1250-0.0156 could reach 148-192 K with $\mu^{*}$=0.10 at 260 GPa. This
suggests that the estimated superconductivity of C-doped $\mathrm{H_{3}S}$ is
much lower than room temperature as predicted in previous studies [23, 22].
The reason for this discrepancy is possibly because different approches were
employed. As for other predicted compounds, the superconductivity-related
information is included in Table 1.

##  IV CONCLUSION

In summary, we have computed the superconductivity of light-elements doped
$\mathrm{H_{3}S}$ using supercell approach within the framework of first-
principle electronic structure. Our simulations indicate that the doping of Na
can lower the dynamically stable pressure of $\mathrm{H_{3}S}$ while the
doping of P can increase the density of states at the Fermi level as well as
the superconductivity of $\mathrm{H_{3}S}$. Remarkably, we found that the
existence of octahedra [$\mathrm{PH_{6}}$] and [$\mathrm{SH_{6}}$] units with
squeezed P-H and S-H bonds in $\mathrm{H_{48}S_{15}P}$ which are likely to be
related to the high density of states at the Fermi level, with the higher
$T_{c}$ of 20-30 K compared with $\mathrm{H_{3}S}$. Furthermore, we have
proposed an estimation approach to reasonably estimate the superconductivity
of the low proportion C-doping $\mathrm{H_{3}S}$ without performing electron-
phonon calculations on a quite large supercell. Our current work may inspire
future work toward searching for high-temperature superconductivity in light-
elements doping systems.

## ACKNOWLEDGMENTS

This work was supported by the Major Program of the National Natural Science
Foundation of China (Grant No. 52090024), National Natural Science Foundation
of China (Grant No. 12074138, 11874175, and 11874176), Fundamental Research
Funds for the Central Universities (Jilin University, JLU), Program for JLU
Science and Technology Innovative Research Team (JLUSTIRT), and The Strategic
Priority Research Program of Chinese Academy of Sciences (Grant No.
XDB33000000). This work used computing facilities at the High-Performance
Computing Centre of Jilin University.

## References

  * Li  _et al._ [2014] Y. Li, J. Hao, H. Liu, Y. Li, and Y. Ma, J. Chem. Phys. 140, 174712 (2014).
  * Duan  _et al._ [2014] D. Duan, Y. Liu, F. Tian, D. Li, X. Huang, Z. Zhao, H. Yu, B. Liu, W. Tian, and T. Cui, Sci. Rep. 4, 6968 (2014).
  * Drozdov  _et al._ [2015] A. P. Drozdov, M. I. Eremets, I. A. Troyan, V. Ksenofontov, and S. I. Shylin, Nature (London) 525, 73 (2015).
  * Li  _et al._ [2015] Y. Li, J. Hao, H. Liu, J. S. Tse, Y. Wang, and Y. Ma, Sci. Rep. 5, 9948 (2015).
  * Liu  _et al._ [2017] H. Liu, I. I. Naumov, R. Hoffmann, N. W. Ashcroft, and R. J. Hemley, Proc. Natl. Acad. Sci. USA 114, 6990 (2017).
  * Peng  _et al._ [2017] F. Peng, Y. Sun, C. J. Pickard, R. J. Needs, Q. Wu, and Y. Ma, Phys. Rev. Lett. 119, 107001 (2017).
  * Somayazulu  _et al._ [2019] M. Somayazulu, M. Ahart, A. K. Mishra, Z. M. Geballe, M. Baldini, Y. Meng, V. V. Struzhkin, and R. J. Hemley, Phys. Rev. Lett. 122, 027001 (2019).
  * Drozdov  _et al._ [2019] A. P. Drozdov, P. P. Kong, V. S. Minkov, S. P. Besedin, M. A. Kuzovnikov, S. Mozaffari, L. Balicas, F. F. Balakirev, D. E. Graf, V. B. Prakapenka, E. Greenberg, D. A. Knyazev, M. Tkacz, and M. I. Eremets, Nature (London) 569, 528 (2019).
  * Semenok  _et al._ [2020] D. V. Semenok, A. G. Kvashnin, A. G. Ivanova, V. Svitlyk, V. Y. Fominski, A. V. Sadakov, O. A. Sobolevskiy, V. M. Pudalov, I. A. Troyan, and A. R. Oganov, Mater. Today 33, 36–44 (2020).
  * Kong  _et al._ [2019] P. P. Kong, V. S. Minkov, M. A. Kuzovnikov, S. P. Besedin, A. P. Drozdov, S. Mozaffari, L. Balicas, F. F. Balakirev, V. B. Prakapenka, E. Greenberg, D. A. Knyazev, and M. I. Eremets, (2019), arXiv:1909.10482 .
  * Sun  _et al._ [2019] Y. Sun, J. Lv, Y. Xie, H. Liu, and Y. Ma, Phys. Rev. Lett. 123, 097001 (2019).
  * Snider  _et al._ [2020] E. Snider, N. Dasenbrock-Gammon, R. McBride, M. Debessai, H. Vindana, K. Vencatasamy, K. V. Lawler, A. Salamat, and R. P. Dias, Nature (London) 586, 373 (2020).
  * Flores-Livas  _et al._ [2020] J. A. Flores-Livas, L. Boeri, A. Sanna, G. Profeta, R. Arita, and M. Eremets, Phys. Rep. 856, 1 (2020), a perspective on conventional high-temperature superconductors at high pressure: Methods and materials.
  * Lv  _et al._ [2020] J. Lv, Y. Sun, H. Liu, and Y. Ma, Matter Radiat. Extremes 5, 068101 (2020).
  * Zurek and Bi [2019] E. Zurek and T. Bi, J. Chem. Phys. 150, 050901 (2019).
  * Wang  _et al._ [2012] H. Wang, J. S. Tse, K. Tanaka, T. Iitaka, and Y. Ma, Proc. Natl. Acad. Sci. USA 109, 6463 (2012).
  * Ma  _et al._ [2021] L. Ma, K. Wang, Y. Xie, X. Yang, Y. Wang, M. Zhou, H. Liu, G. Liu, H. Wang, and Y. Ma, (2021), arXiv:2103.16282 .
  * Li  _et al._ [2021] Z. W. Li, X. He, C. L. Zhang, S. J. Zhang, S. M. Feng, X. C. Wang, R. C. Yu, and C. Q. Jin, (2021), arXiv:2103.16917 .
  * Sun  _et al._ [2020] Y. Sun, Y. Tian, B. Jiang, X. Li, H. Li, T. Iitaka, X. Zhong, and Y. Xie, Phys. Rev. B 101, 174102 (2020).
  * Cui  _et al._ [2020] W. Cui, T. Bi, J. Shi, Y. Li, H. Liu, E. Zurek, and R. J. Hemley, Phys. Rev. B 101, 134504 (2020).
  * Hu  _et al._ [2020] S. X. Hu, R. Paul, V. V. Karasiev, and R. P. Dias, (2020), arXiv:2012.10259 .
  * Dogan and Cohen [2021] M. Dogan and M. L. Cohen, Physica C 583, 1353851 (2021).
  * Wang  _et al._ [2021a] T. Wang, M. Hirayama, T. Nomoto, T. Koretsune, R. Arita, and J. A. Flores-Livas, (2021a), arXiv:2104.03710 .
  * Bykova  _et al._ [2021] E. Bykova, M. Bykov, S. Chariton, V. B. Prakapenka, K. Glazyrin, A. Aslandukov, A. Aslandukova, G. Criniti, A. Kurnosov, and A. F. Goncharov, Phys. Rev. B 103, L140105 (2021).
  * Du  _et al._ [2021] M. Du, Z. Zhang, T. Cui, and D. Duan1, (2021), arXiv:2107.10485 .
  * Ge  _et al._ [2020] Y. Ge, F. Zhang, R. P. Dias, R. J. Hemley, and Y. Yao, Mater. Today Phys. 15, 100330 (2020).
  * Nordheim [1931] L. Nordheim, Ann. Phys. 401, 607 (1931).
  * Kresse and Furthmüller [1996] G. Kresse and J. Furthmüller, Phys. Rev. B 54, 11169 (1996).
  * Perdew  _et al._ [1996] J. P. Perdew, K. Burke, and M. Ernzerhof, Phys. Rev. Lett. 77, 3865 (1996).
  * Blöchl [1994] P. E. Blöchl, Phys. Rev. B 50, 17953 (1994).
  * Monkhorst and Pack [1976] H. J. Monkhorst and J. D. Pack, Phys. Rev. B 13, 5188 (1976).
  * Wang  _et al._ [2021b] V. Wang, N. Xu, J. C. Liu, G. Tang, and W.-T. Geng, (2021b), arXiv:1908.08269 .
  * Vanderbilt [1990] D. Vanderbilt, Phys. Rev. B 41, 7892 (1990).
  * Methfessel and Paxton [1989] M. Methfessel and A. T. Paxton, Phys. Rev. B 40, 3616 (1989).
  * Allen and Dynes [1975] P. B. Allen and R. C. Dynes, Phys. Rev. B 12, 905 (1975).
  * Migdal [1958] A. B. Migdal, Sov. Phys. JETP 7, 996 (1958).
  * Eliashberg [1960] G. M. Eliashberg, Sov. Phys. JETP 11, 696 (1960).
  * Scalapino  _et al._ [1966] D. J. Scalapino, J. R. Schrieffer, and J. W. Wilkins, Phys. Rev. 148, 263 (1966).
  * Sanna  _et al._ [2012] A. Sanna, S. Pittalis, J. K. Dewhurst, M. Monni, S. Sharma, G. Ummarino, S. Massidda, and E. K. U. Gross, Phys. Rev. B 85, 184514 (2012).
  * [40] The Elk Code, http://elk.sourceforge.net/.
  * [41] See supplemental material at url for analysis of allen-dynes-mcmillan equation, estimation method and results for $\mathrm{C}$ doped $\mathrm{H_{3}S}$, crystal structures, electronic properties and phonon properties.
  * Ge  _et al._ [2016] Y. Ge, F. Zhang, and Y. Yao, Phys. Rev. B 93, 224513 (2016).
  * Nakanishi  _et al._ [2018] A. Nakanishi, T. Ishikawa, and K. Shimizu, J. Phys. Soc. Jpn. 87, 124711 (2018).
  * Quan and Pickett [2016] Y. Quan and W. E. Pickett, Phys. Rev. B 93, 104526 (2016).
  * Hopfield [1969] J. J. Hopfield, Phys. Rev. 186, 443 (1969).
  * Boeri  _et al._ [2004] L. Boeri, J. Kortus, and O. K. Andersen, Phys. Rev. Lett. 93, 237002 (2004).