Periodicities of Grover Walks on Distance-Regular Graphs

Abstract

Characterization of some classes of graphs inducing periodic Grover walks have been studied for recent years. In particular, for the strongly regular graphs, it has been known that there are only three kinds of such graphs. As an extension of this result, we focus on the periodicity of the Grover walks on distance-regular graphs. The distance-regular graph is regarded as a kind of generalization of the strongly regular graph. In this paper, we find some classes of distance-regular graphs admitting a periodic Grover walk and obtain a useful necessary condition to induce periodic Grover walks. Also, we apply this necessary condition to give another proof for the classification of the strongly regular graphs.

Appendix

In this part, we prove that distance-regular graphs with quotient matrices (21), and (22) are uniquely determined as $K_{k, k}$, and $K_{m, m, m}$, respectively.

First, we consider (21):

$$\begin{aligned} Q=\left( \begin{array}{ccc} 0 &{} k &{} 0 \\ 1 &{} 0 &{} k-1\\ 0 &{} k &{} 0 \end{array} \right) . \end{aligned}$$

Let G be a distance-regular graph with quotient matrix (21). Then G is a k-regular graph. We fix $x \in V(G)$. Then we have $|\varGamma _{1}(x)|=k, |\varGamma _{2}(x)|=k-1$ by the relation of

$$\begin{aligned} b_{j} |\varGamma _{j}(x)|=c_{j+1} |\varGamma _{j+1}(x)|, \end{aligned}$$

(23)

for $j \in \{0, 1, 2\}$ [1] and $|\varGamma _{0}(x)|=1$, where $\varGamma _{j}(x)$ is defined in Sect. 2. So any vertex in $\varGamma _{1}(x)$ is adjacent to all the vertices in $\varGamma _{2}(x)$ and vice versa, since $b_{1}=k-1$ and $c_{2}=k$. Put

$$\begin{aligned} V_{1}=&\varGamma _{0}(x) \cup \varGamma _{2}(x),\\ V_{2}=&\varGamma _{1}(x). \end{aligned}$$

Then $|V_{1}|=|V_{2}|=k$, and $\{ V_{1}, V_{2} \}$ becomes the complete bi-partition. Therefore, G is determined as $K_{k, k}$.

Next, we consider (22):

$$\begin{aligned} Q=\left( \begin{array}{ccc} 0 &{} 2m &{} 0 \\ 1 &{} m &{} m-1\\ 0 &{} 2m &{} 0 \end{array} \right) . \end{aligned}$$

Let G be a distance-regular graph with quotient matrix (22). Then G is a 2m-regular graph. We fix $x \in V(G)$. Then it follows that $|\varGamma _{0}(x)|=1, |\varGamma _{1}(x)|=2m$, and $|\varGamma _{2}(x)|=m-1$ from (23). For a fixed vertex $u \in \varGamma _{1}(x)$, put

$$\begin{aligned} V_{1}=&\varGamma _{0}(x) \cup \varGamma _{2}(x),\\ V_{2}=&N(u)\cap \varGamma _{1}(x),\\ V_{3}=&\varGamma _{1}(x){\backslash } V_{2}. \end{aligned}$$

Then we have $|V_{1}|=|V_{2}|=|V_{3}|=m$ since $|\varGamma _{2}(x)|=m-1$, $a_{1}=m$ and $u \in V_{3}$. We show that $\{V_{1}, V_{2}, V_{3} \}$ becomes the complete tri-partition. From the definition of $\varGamma _{1}(x)$, x is adjacent to all the vertices in both of $V_{2}$ and $V_{3}$. In addition, any vertex in $\varGamma _{2}(x)$ is adjacent to all the vertices in $\varGamma _{1}(x)$ since $c_{2}=|\varGamma _{1}(x)|=2m$. So we obtain that any vertex in $V_{1}$ is adjacent to all the vertices in $V_{2} \cup V_{3}$. Then no two vertices in $V_{1}$ are adjacent each other and we will show it for both of $V_{2}$ and $V_{3}$. Suppose that there exist $u_{1}, u_{2} \in V_{2}$ such that $u_{1} \sim u_{2}$. Since $|V_{3}|=m$ and m edges from $u_{1}$ extend to $V_{1}$, there exists a vertex $w(\ne u) \in V_{3}$ such that $u_{1} \not \sim w$. It follows that $u \not \sim w$ since m edges extend from u to $V_{1}$ and the remaining m edges extend from u to $V_{2}$. Now we retake $\varGamma _{0}(w), \varGamma _{1}(w), \varGamma _{2}(w)$. Since both of $u, u_{1}$ are not adjacent to w, it follows that $u, u_{1} \in \varGamma _{2}(w)$. Moreover, it follows that $u \sim u_{1}$ from the definition of $V_{2}$, which contradicts $a_{2}=0$. So it follows that any vertex in $V_{2}$ is not adjacent to another vertex in $V_{2}$ and so is any vertex in $V_{3}$ since $|V_{3}|=m$. Hence, $\{V_{1}, V_{2}, V_{3} \}$ becomes the complete tri-partition and G is uniquely determined as $K_{m, m, m}$.