# Regular Graphs of Degree at most Four that Allow Two Distinct Eigenvalues

Wayne Barrett Department of Mathematics, Brigham Young University, Provo, UT
<EMAIL_ADDRESS> Shaun Fallat Department of Mathematics and
Statistics, University of Regina, Regina, Saskatchewan, CA
(shaun.fallat@uregina.ca)Corresponding Author Veronika Furst Department of
Mathematics, Fort Lewis College, Durango, CO<EMAIL_ADDRESS>Shahla
Nasserasr School of Mathematical Sciences, Rochester Institute of Technology,
Rochester, NY<EMAIL_ADDRESS>Brendan Rooney School of Mathematical Sciences,
Rochester Institute of Technology, Rochester, NY<EMAIL_ADDRESS>Michael Tait
Department of Mathematics & Statistics, Villanova University, Villanova, PA
<EMAIL_ADDRESS>
###### Abstract

For an $n\times n$ matrix $A$, let $q(A)$ be the number of distinct
eigenvalues of $A$. If $G$ is a connected graph on $n$ vertices, let
$\mathcal{S}(G)$ be the set of all real symmetric $n\times n$ matrices
$A=[a_{ij}]$ such that for $i\neq j$, $a_{ij}=0$ if and only if $\\{i,j\\}$ is
not an edge of $G$. Let $q(G)={\rm min}\\{q(A)\,:\,A\in\mathcal{S}(G)\\}$.
Studying $q(G)$ has become a fundamental sub-problem of the inverse eigenvalue
problem for graphs, and characterizing the case for which $q(G)=2$ has been
especially difficult. This paper considers the problem of determining the
regular graphs $G$ that satisfy $q(G)=2$. The resolution is straightforward if
the degree of regularity is $1,2,$ or $3$. However, the $4$-regular graphs
with $q(G)=2$ are much more difficult to characterize. A connected $4$-regular
graph has $q(G)=2$ if and only if either $G$ belongs to a specific infinite
class of graphs, or else $G$ is one of fifteen $4$-regular graphs whose number
of vertices ranges from $5$ to $16$. This technical result gives rise to
several intriguing questions.

Keywords inverse eigenvalue problem for graphs, orthogonality, $q$-parameter,
regular graphs.

AMS subject classification 05C50, 15A29, 15A18.

##  1 Introduction

For any connected graph $G$ on $n$ vertices, let $\mathcal{S}(G)$ denote the
set of all real symmetric $n\times n$ matrices $A=[a_{ij}]$ where $a_{ij}=0$
if and only if $\\{i,j\\}$ is not an edge in $G$, and the entries $a_{ii}$ can
take any value. The _inverse eigenvalue problem_ for a graph $G$ asks to
determine all possible spectra of matrices in $\mathcal{S}(G)$ [5, 14].

This problem and several of its sub-problems have been studied extensively.
One of these sub-problems is to consider all possible multiplicity lists of
eigenvalues of matrices in $\mathcal{S}(G)$. If we look at the multiplicity
lists of eigenvalues of all matrices in $\mathcal{S}(G)$ as lists of numbers,
the shortest length among all these lists is the minimum number of distinct
eigenvalues of matrices in $\mathcal{S}(G)$. This parameter is denoted by
$q(G)$ and has been studied in [2, 7, 15, 16, 17]. In this paper, we
investigate the problem of determining which regular connected graphs $G$ have
a matrix in $\mathcal{S}(G)$ with exactly two distinct eigenvalues, that is,
with $q(G)=2$.

The connected graphs $G$ with $q(G)=n-1$ or $n$ have been characterized, see
[7]. Graphs with $q(G)=2$ are much harder to describe; for example, there is
no forbidden subgraph characterization of graphs with $q(G)=2$, as implied by
Theorem 5.2 in [2]. It is known that $q(G)=2$ if and only if there is an
orthogonal matrix in $\mathcal{S}(G)$ [2], and so studying graphs $G$ on $n$
vertices with $q(G)=2$ is equivalent to studying all possible zero patterns of
$n\times n$ symmetric orthogonal matrices.

A graph $G$ must have a sufficiently large number of edges to satisfy
$q(G)=2$. In [6], we showed that a connected graph $G$ on $n$ vertices with
$q(G)=2$ has at least $2n-4$ edges. We also characterized the graphs for which
equality is attained. This result immediately implies that the number of
$r$-regular graphs with $r\in\\{2,3\\}$ is finite, and in Section 2 we
characterize these graphs. When considering $4$-regular graphs with $q(G)=2$,
the difficulty increases significantly. Our main theorem (Theorem 2.4)
characterizes all connected $4$-regular graphs with $q(G)=2$.

Throughout this paper, we only consider connected, simple, undirected graphs.

###  1.1 Preliminaries

One of the common ways to give a lower bound on $q(G)$ is to find a unique
shortest path between vertices. This technique, specialized to the case
$q(G)=2$, is explained in the following lemma, which is a corollary of Theorem
3.2 in [2].

######  Lemma 1.1.

Let $G$ be a connected graph with $q(G)=2$. If $xuy$ is a path of length $2$,
then either $x\sim y$ or there is another path $xvy$ of length $2$ between $x$
and $y$.

In [6], we used this lemma extensively in combination with a breadth-first
search of a graph, and we use this strategy here as well. Given a fixed vertex
$v$, we perform a breadth-first search from $v$. Denote the vertices at
distance exactly $i$ from $v$ by $N_{i}(v)$, and call this set the $i$th
distance set from $v$. We use $\epsilon(v)$ to denote the eccentricity of $v$,
which is the maximum distance from $v$ to any vertex in the graph. The
distance sets from $v$ partition the vertex set of $G$ as

$V(G)=\bigcup_{i=0}^{\epsilon(v)}N_{i}(v),$

which we call the _distance partition_ of $G$ with respect to $v$. If $u\in
N_{i}(v)$ and $w\in N_{i+1}(v)$ and $u\sim w$, we call $u$ a predecessor of
$w$ and we call $w$ a successor of $u$. A terminal vertex is a vertex with no
successors.

Assume that $G$ is a graph with $q(G)=2$ and consider the distance partition
from a vertex $v$. If a vertex $u$ is in $N_{i}(v)$ for some $i\geq 2$, then
by Lemma 1.1, it must have at least two predecessors, as otherwise there would
be a unique shortest path of length $2$ from $u$ to a vertex in $N_{i-2}(v)$.
If $G$ is a $4$-regular graph on $n$ vertices, then there are $n-5$ vertices
in

$\bigcup_{i=2}^{\epsilon(v)}N_{i}(v)=V(G)\setminus(\\{v\\}\cup N_{1}(v)),$

and each of these vertices has at least two predecessors so there are at least
$2(n-5)$ edges incident to these vertices. With the 4 edges incident to $v$,
this accounts for $2n-6$ of the $2n$ edges of $G$. We call the remaining six
edges extra edges, and throughout the paper we consider the possible locations
of these six extra edges.

We use standard graph theory terminology and notations. Often we abbreviate an
edge $\\{u,v\\}\in E(G)$ as $uv$ for vertices $u,v\in V(G)$. For two graphs
$G$ and $H$ with vertex sets $V(G)$ and $V(H)$, respectively, the Cartesian
product $G\Box H$ is the graph with vertex set $V(G)\times V(H)$ and
$(g_{1},h_{1})$ adjacent to $(g_{2},h_{2})$ if either $g_{1}=g_{2}$ and
$h_{1}h_{2}\in E(H)$, or $h_{1}=h_{2}$ and $g_{1}g_{2}\in E(G)$. The complete
graph on $n$ vertices, complete bipartite graph on partite sets of sizes $m$
and $n$, the cycle on $n$ vertices, the path on $n$ vertices, and the
hypercube graph (the graph on $2^{n}$ vertices obtained by an $n$-fold
Cartesian product of $K_{2}$ with itself) are denoted by $K_{n}$, $K_{m,n}$,
$C_{n}$, $P_{n}$, $Q_{n}$, respectively. The circulant graph $G=C(n,\pm i,\pm
j)$ is the graph with vertex set $V(C(n,\pm i,\pm j))=\mathbb{Z}/n\mathbb{Z}$
that has edges $\\{t,t\pm i\\}$ and $\\{t,t\pm j\\}$ for all $t\in V(G)$.

Let $G$ be a graph with $v\in V(G)$. A graph $\operatorname{jdup}(G,v)$ is
constructed from $G$ by _joined duplicating_ a vertex $v\in V(G)$ if
$V(\operatorname{jdup}(G,v))=V(G)\cup\\{u\\}$ and
$E(\operatorname{jdup}(G,v))=E(G)\cup\\{uw\,:\,w\in\\{v\\}\cup N_{1}(v)\\}$.
From Lemma 2.9 in [16], $q(\operatorname{jdup}(G,v))\leq q(G)$ for any vertex
$v$ in a connected graph $G$.

######  Lemma 1.2.

[Lemma 2.3, [1]] Let $G$ be a connected graph on $n$ vertices with $q(G)=2$.
If $S$ is an independent set of vertices, then $|S|\leq k$ where $k$ is the
least integer such that there is a matrix in $\mathcal{S}(G)$ with two
distinct eigenvalues of multiplicities $k$ and $n-k$.

######  Lemma 1.3.

Let

$M=\left[\begin{array}[]{cc}C&B\\\ B^{T}&D\end{array}\right]$

where $C$ is an $m\times m$ symmetric matrix, $B=[b_{1}\ldots\ b_{n}]$ has no
zero columns, and $D=\operatorname{diag}(d_{1},\ldots,d_{n})$. If $M$ is
orthogonal, then $n\leq m$, the vectors $b_{1},\ldots,b_{n}$ are pairwise
orthogonal, and each $b_{i}$ is a $(-d_{i})$-eigenvector for $C$.

###### Proof.

Consider the last $n$ columns of $M$. Since $D$ is diagonal, these columns are
pairwise orthogonal if and only if $n\leq m$ and the vectors
$b_{1},\ldots,b_{n}$ are pairwise orthogonal.

Second, expanding $M^{2}=I$ we have

$M^{2}=\left[\begin{array}[]{rr}C^{2}+BB^{T}&CB+BD\\\
B^{T}C+DB^{T}&B^{T}B+D^{2}\end{array}\right]=\left[\begin{array}[]{cc}I_{m}&0\\\
0&I_{n}\end{array}\right].$

From the $(1,2)$-block we see $CB+BD=0$. Rearranging this equation we have

$[Cb_{1}\ldots Cb_{n}]=-[d_{1}b_{1}\ldots d_{n}b_{n}]$

from which it follows that each $b_{i}$ is a $(-d_{i})$-eigenvector for $C$. ∎

As an illustration of Lemma 1.3, suppose $G$ is a connected bipartite graph
with bipartition $V=V_{1}\cup V_{2}$. Further assume that $|V_{1}|=|V_{2}|$.
It follows that if $q(G)=2$, then there exists a matrix $M\in S(G)$, where

$M=\left[\begin{array}[]{cc}C&B\\\ B^{T}&D\end{array}\right],$

where $M^{2}=I$, and both $C$ and $D$ are diagonal matrices. Applying Lemma
1.3 we have that $B$ must be a matrix with orthogonal rows and columns. In
fact, the converse also holds in this case. If such an orthogonal matrix $B$
exists, then the matrix

$M=\frac{1}{\sqrt{2}}\left[\begin{array}[]{cc}I&B\\\
B^{T}&-I\end{array}\right]$

is orthogonal and hence $q(G)=2$.

##  2 Certain Regular Graphs that Allow Two Distinct Eigenvalues

From Theorem 3.1 in [6], if a connected graph $G$ has fewer than $2n-4$ edges,
then $q(G)>2$. This implies that there are only finitely many $r$-regular
graphs with $r\leq 3$ that satisfy $q(G)=2$. We describe them below.

######  Lemma 2.1.

Let $r\leq 3$. If $G$ is a connected $r$-regular graph with $q(G)=2$, then $G$
has at most $8/(4-r)$ vertices.

###### Proof.

In order for $G$ to have $q(G)=2$, $G$ has to have at least $2n-4$ edges. So
we have the inequality

$(r/2)n\geq 2n-4.$

Since $0<r/2<2$, this simplifies to $n\leq 8/(4-r)$. ∎

######  Corollary 2.2.

If $G$ is a connected $r$-regular graph with $q(G)=2$ for some $r\leq 3$, then
$G$ is one of:

  1. (1)

$K_{2}$;

  2. (2)

$K_{3}$ or $C_{4}$; or,

  3. (3)

$K_{4}$, $K_{3,3}$, $K_{3}\Box K_{2}$, or $Q_{3}$.

###### Proof.

The graph $K_{2}$ is the only connected $1$-regular graph and has
$q(K_{2})=2$. The only connected $2$-regular graphs on $n\leq 4$ vertices are
$K_{3}$ and $C_{4}$ and both have $q(G)=2$. By Lemma 2.1, a $3$-regular graph
with $q(G)=2$ has $4,6$ or $8$ vertices. If $n=4$, $G=K_{4}$ and $q(G)=2$. If
$n=6$, the complement of $G$ is $2$-regular and so must be $C_{6}$ or
$2K_{3}$. Thus $G$ is either $K_{3}\Box K_{2}$ or $K_{3,3}$, respectively,
both of which have $q(G)=2$ from Corollaries 6.5 and 6.8 in [2]. If $n=8$, $G$
has $12=2(8)-4$ edges. Thus by Theorem 3.1 from [6], $G\cong Q_{3}$. ∎

We now proceed with the main purpose of this paper, to characterize the
$4$-regular graphs $G$ with $q(G)=2$. We begin by defining an infinite family
of graphs called closed candles which are analogs to the single-ended and
double-ended candles in [6]. For $k\geq 3$ the _closed candle_ , $H_{k}$, is
constructed from $2C_{k}$ as follows. Label the vertices of one $C_{k}$ with
the odd integers from 1 to $2k-1$ and the other with the even integers from 2
to $2k$. Insert $2k$ additional edges between the two $C_{k}$’s according to
the rule: $i$ is adjacent to $j$, $i$ odd, $j$ even if $j-i=3$, $j-i=-1$, or
$j=2$, $i=2k-1$, or $i=1$, $j=2k$. Thus $H_{k}$ is a $4$-regular graph. The
graph $H_{10}$ is shown in Figure 1.

$1$$17$$15$$13$$7$$5$$3$$19$$11$$9$$2$$18$$16$$12$$10$$14$$20$$6$$4$$8$

Figure 1: Closed candle $H_{10}$.

In the proof of Theorem 2.4, we will consider induced subgraphs that have the
same structure as a closed candle. A _candle section_ is a graph with vertices
$u_{1},\ldots,u_{t},v_{1},\ldots,v_{t}$ with edges $u_{i}u_{i+1}$,
$v_{i}v_{i+1}$, $u_{i+1}v_{i}$, and $u_{i}v_{i+1}$ for $1\leq i\leq t-1$, see
Figure 2.

$u_{1}$$u_{2}$$u_{3}$$u_{t-2}$$u_{t-1}$$u_{t}$$v_{t}$$v_{t-1}$$v_{t-2}$$v_{3}$$v_{2}$$v_{1}$$\ldots$$\ldots$$\ldots$
Figure 2: Candle section.

The following lemma gives a construction of orthogonal matrices for the closed
candles.

######  Lemma 2.3.

For all $k\geq 3$, we have $q(H_{k})=2$.

###### Proof.

To see that the graphs $H_{k}$ for $k\geq 3$ achieve two distinct eigenvalues,
we construct orthogonal matrices for this family of graphs.

Let

$\displaystyle R=\left[\begin{array}[]{rr}-1&1\\\ 1&-1\end{array}\right],\
S=\left[\begin{array}[]{rr}1&1\\\ -1&-1\end{array}\right],\
J=\left[\begin{array}[]{rr}\phantom{-}1&1\\\
1&\phantom{-}1\end{array}\right],\ \textrm{and}\
O=\left[\begin{array}[]{rr}0&0\\\ 0&0\end{array}\right].$

We consider two cases for $k$ and construct the corresponding matrices $W$.
Here all of the blocks are $2\times 2.$ The matrix in each case is symmetric
so the blocks below the diagonal blocks are transposes of the corresponding
matrices.

_Case 1:_ $n=2k$ and $k\geq 4$ is even.

$W_{ij}=\begin{cases}R,&\textrm{for}\,\,(i,j)=(1,2),(3,4),\ldots,(k-3,k-2),(k-1,k)\\\
J,&\textrm{for}\,\,(i,j)=(2,3),(4,5),\ldots,(k-2,k-1)\\\
J,&\textrm{for}\,\,(i,j)=(1,k)\\\ O,&\textrm{otherwise}\\\ \end{cases}$

_Case 2:_ $n=2k$ and $k\geq 3$ is odd.

First, note that when $k=3$, the graph $H_{3}$ is the octahedron (the graph
obtained from $K_{6}$ by deleting a perfect matching). By Corollary 6.9 in
[8], we have $q(H_{3})=q(G204)=2$. Now if $k\geq 5$, we construct the matrices
as follows.

$W_{ij}=\begin{cases}J,&\textrm{for}\,\,(i,j)=(1,2),(3,4),\ldots,(k-4,k-3)\\\
R,&\textrm{for}\,\,(i,j)=(2,3),(4,5),\ldots,(k-5,k-4),\ \ {\rm and}\
(k-2,k-1);\\\ S,&\textrm{for}\,\,(i,j)=(1,k),(k-3,k-2)\\\
S^{T},&\textrm{for}\,\,(i,j)=(k-1,k)\\\ O,&\textrm{otherwise}\\\ \end{cases}$

Each row of $W$ has Euclidean length $2$. Since each of the $2\times 4$
matrices $[J\;S]$, $[J\;R]$, $[S^{T}\;R]$, $[S\;S^{T}]$ have orthogonal rows,
each pair of rows of $W$ coming from the same block are orthogonal. For $i\neq
j$, the $(i,j)$-block of $W^{2}$ is one of $JR$, $JS$, $SR$, $S^{2}$ or their
transposes. In each of the cases the matrix is the zero matrix. Hence
$W^{T}W=W^{2}=4I$. We conclude that $\frac{1}{2}W$ is an orthogonal matrix
with whose graph is the closed candle on $n=2k$ vertices. ∎

For example, the matrices for $k=4$ and $k=5$ are respectively

$\left[\begin{array}[]{ccccc}O&R&O&J\\\ R&O&J&O\\\ O&J&O&R\\\ J&O&R&O\\\
\end{array}\right]\quad\mbox{and}\quad\left[\begin{array}[]{ccccc}O&J&O&O&S\\\
J&O&S&O&O\\\ \\\\[-10.0pt] O&S^{T}&O&R&O\\\ O&O&R&O&S^{T}\\\
S^{T}&O&O&S&O\end{array}\right];$

for $k=6$ and $k=7$, the matrices are respectively

$\left[\begin{array}[]{cccccc}O&R&O&O&O&J\\\ R&O&J&O&O&O\\\ O&J&O&R&O&O\\\
O&O&R&O&J&O\\\ O&O&O&J&O&R\\\ J&O&O&O&R&O\\\
\end{array}\right]\quad\mbox{and}\quad\left[\begin{array}[]{ccccccc}O&J&O&O&O&O&S\\\
J&O&R&O&O&O&O\\\ O&R&O&J&O&O&O\\\ O&O&J&O&S&O&O\\\ \\\\[-10.0pt]
O&O&O&S^{T}&O&R&O\\\ O&O&O&O&R&O&S^{T}\\\
S^{T}&O&O&O&O&S&O\end{array}\right].$

Note that the closed candle $H_{k}$ has independence number $k$ if $k$ is
even, and $k-1$ if $k$ is odd. By Lemma 1.2 when $k$ is even the only
achievable multiplicity list for two distinct eigenvalues is $[k,k]$; when $k$
is odd, the only achievable multiplicity lists for two distinct eigenvalues
are $[k,k]$ and $[k-1,k+1]$.

Lemma 2.3 provides an infinite family of $4$-regular graphs with $q(G)=2$. Our
main theorem below characterizes all $4$-regular graphs $G$ for which
$q(G)=2$.

######  Theorem 2.4.

If $G$ is a connected 4-regular graph with $q(G)=2$, then $G$ is either:

  1. (1)

$K_{5}$;

  2. (2)

one of the graphs $R_{7,1}$, $R_{8,2}$, $R_{8,3}$, $R_{8,4}$, $R_{8,5}$,
$R_{8,6}$ from Figure 3;

  3. (3)

$K_{3}\Box C_{4}$, $K_{3,3}\Box K_{2}$, one of the graphs $R_{10,2}$,
$R_{10,3}$, $R_{10,4}$, $R_{12,3}$, $R_{14,1}$ from Figure 4;

  4. (4)

$Q_{4}$; or,

  5. (5)

a closed candle $H_{k}$ for some $k\geq 3$.

_Notes:_ The graphs listed in items (1) through (4) of Theorem 2.4 have
diameter 1 through 4 respectively. The graph $R_{7,1}\cong C(7,\pm 1,\pm 2)$,
the graph $R_{8,5}\cong K_{4}\Box K_{2}$, and the graph $R_{8,6}\cong C(8,\pm
1,\pm 2)$. The graph $R_{10,3}$ is the graph obtained from $Q_{3}$ by joined
duplicating a pair of antipodal vertices (in [6] we referred to this graph as
$Q_{3}^{\prime}$). The graph $R_{10,4}\cong C(10,\pm 1,\pm 3)$, and the graph
$R_{12,3}\cong C(12,\pm 1,\pm 3)$. The graph $R_{14,1}$ appears in [19] as
$S_{14}$. Moreover $R_{14,1}$ is the Cayley graph for the dihedral group
$D_{7}$ (with generators $\rho$ and $\varphi$ satisfying
$\rho^{2}=\varphi^{7}=\varepsilon$ and $\rho\varphi=\varphi^{6}\rho$) with
connection set $\\{\rho,\varphi\rho,\varphi^{2}\rho,\varphi^{4}\rho\\}$. It is
also the point-block incidence graph of the non-trivial square $2-(7,4,2)$
design and is distance regular with diameter $3$, see [9]. The sporadic graphs
$R_{6,1}$, $R_{8,1}$, and $R_{10,1}$ in Figure 3 are $H_{3}$, $H_{4}$, and
$H_{5}$, respectively, so appear in item (5) of Theorem 2.4. Also note that
the closed candles are all circulants. For $k\geq 3$, it can be verified that
$H_{k}\cong C(2k,\pm 1,\pm(k-1))$.

The proof of Theorem 2.4 is split over Sections 3, 4, and 5.

##  3 Proof of Theorem 2.4 for 4-Regular Graphs with Small Diameter

In this section we prove items (1) and (2) of Theorem 2.4 for graphs with
diameter at most $2$. The only $4$-regular graph with diameter $1$ is $K_{5}$,
and $q(K_{5})=2$, so we focus on $4$-regular graphs with diameter $2$. We
begin by enumerating the $4$-regular graphs $G$ with diameter $2$ for which
$q(G)=2$ is not ruled out by Lemma 1.1.

######  Lemma 3.1.

If $G$ is a connected $4$-regular graph with diameter $2$ such that $q(G)=2$,
then $6\leq|V(G)|\leq 10$.

###### Proof.

Let $G$ be a connected $4$-regular graph with diameter $2$. Consider an
arbitrary vertex $v$ in $G$ and the distance partition of $V(G)$ from $v$. In
order for $G$ to have $q(G)=2$, it must be the case that each $x\in N_{2}(v)$
has at least two neighbors in $N_{1}(v)$, otherwise there is a unique path of
length 2 between $x$ and $v$. Let $X$ be the set of edges between $N_{1}(v)$
and $N_{2}(v)$. Then

$2|N_{2}(v)|\leq|X|\leq 3|N_{1}(v)|=12.$

So $|N_{2}(v)|\leq 6$ and $G$ has at most $1+4+6=11$ vertices. This
establishes $6\leq|V(G)|\leq 11$.

We now show the upper bound can be improved to $10$. Consider a $4$-regular
graph $G$ with $11$ vertices and diameter $2$. Using the notation above, we
see $|N_{2}(v)|=6$, and $|X|=12$. So every vertex in $N_{1}(v)$ has exactly
three neighbors in $N_{2}(v)$, and every vertex in $N_{2}(v)$ has exactly two
neighbors in $N_{1}(v)$. In particular, this means the subgraph $H$ of $G$
induced by $N_{2}(v)$ is $2$-regular. So we have two cases: either $H$ is a
$6$-cycle, or $H$ is the disjoint union of two $3$-cycles.

_Case 1: $H\cong C_{6}$_

Let the vertices of $H$ be $x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$, $x_{5}$,
$x_{6}$ in cyclic order. Note that $H$ is bipartite, and in $H$ there is a
unique shortest path of length $2$ between any two vertices in the same
partite set. Since there can be no unique shortest path of length $2$ in $G$,
the edges of $X$ must supply an additional path of length $2$ between every
pair of vertices in each partite set.

Let $N_{1}(v)=\\{v_{1},v_{2},v_{3},v_{4}\\}$. Since $v_{i}vv_{j}$ is a path of
length $2$, in order for this path not to be unique there must be some $x_{k}$
that is adjacent to both $v_{i}$ and $v_{j}$. In particular, this means we
cannot have some $v_{i}$ whose neighbors are $\\{x_{1},x_{3},x_{5}\\}$ and
some $v_{j}$ whose neighbors are $\\{x_{2},x_{4},x_{6}\\}$. If there is no
$v_{i}$ whose neighbors are $\\{x_{1},x_{3},x_{5}\\}$, then
$\\{x_{1},x_{3},x_{5}\\}$ together with the common neighbor of
$\\{x_{1},x_{3}\\}$, the common neighbor of $\\{x_{3},x_{5}\\}$ and the common
neighbor of $\\{x_{1},x_{5}\\}$ form a $6$-cycle. Without loss of generality,
suppose this $6$-cycle is $(v_{1},x_{1},v_{2},x_{3},v_{3},x_{5})$. Then, in
order for each pair of vertices in $\\{x_{2},x_{4},x_{6}\\}$ to have a common
neighbor, we must have $v_{4}$ adjacent to each of $\\{x_{2},x_{4},x_{6}\\}$.
Thus the edges between $\\{v_{1},v_{2},v_{3}\\}$ and $\\{x_{2},x_{4},x_{6}\\}$
are a perfect matching.

We know $v_{1}$ is matched to one of $x_{2}$, $x_{4}$, or $x_{6}$. We also
know that $v_{1}$ is already adjacent to $x_{1}$ and $x_{5}$. Note that in
$H$, $x_{1}$ is at distance $3$ from $x_{4}$. So if $v_{1}$ is matched to
$x_{4}$, then we have a unique shortest path of length $2$, $x_{1}v_{1}x_{4}$.
Similarly, $x_{5}$ is at distance $3$ from $x_{2}$ in $H$, so if we match
$v_{1}$ to $x_{2}$, we get another unique shortest path of length $2$. Thus
$v_{1}$ must be matched to $x_{6}$. A similar argument shows that $v_{2}$ must
be matched to $x_{2}$, and $v_{3}$ must be matched to $x_{4}$. This accounts
for all of the edges in $X$. But now we see that $v_{1}x_{1}x_{2}$ is a unique
shortest path of length $2$ in $G$.

_Case 2: $H\cong 2C_{3}$_

Let the vertices of $H$ be $x_{1},x_{2},x_{3}$ and $y_{1},y_{2},y_{3}$, where
all of the $x_{i}$’s are adjacent, and all of the $y_{i}$’s are adjacent. Let
$N_{1}(v)=\\{v_{1},v_{2},v_{3},v_{4}\\}$. We know that $x_{1}$ has $2$
neighbors in $N_{1}(v)$. Without loss of generality, suppose $x_{1}$ is
adjacent to $v_{1}$. Then $v_{1}x_{1}x_{2}$ and $v_{1}x_{1}x_{3}$ are paths of
length $2$. In order for them not to be unique shortest paths of length $2$,
we must have at least one of the edges $v_{1}x_{2}$ and $v_{1}x_{3}$. Suppose
$v_{1}$ is adjacent to exactly one of $x_{2}$ and $x_{3}$. Then $v_{1}$ is
adjacent to exactly one of the $y_{i}$ vertices, and we have a unique path
$v_{1}y_{i}y_{j}$ between $v_{1}$ and some $y_{j}$. Thus $v_{1}$ must be
adjacent to both $x_{2}$ and $x_{3}$. If $v_{2}$ is the other neighbor of
$x_{1}$ in $N_{1}(v)$, then following the same argument as for $v_{1}$, we
must also have edges $v_{2}x_{2}$ and $v_{2}x_{3}$. This accounts for all
edges in $X$ with ends $v_{1}$ and $v_{2}$, and all edges in $X$ with ends
$x_{1}$, $x_{2}$, or $x_{3}$. Thus the remaining edges in $X$ are all possible
edges between $\\{v_{3},v_{4}\\}$ and $\\{y_{1},y_{2},y_{3}\\}$. But now
$v_{1}vv_{3}$ is a unique shortest path of length $2$. ∎

Since there are only $84$ connected $4$-regular graphs with order $6\leq n\leq
10$ [20], we can generate the list of $4$-regular graphs with diameter $2$ for
which $q(G)=2$ is not ruled out by Lemma 1.1. We do this by:

  1. (1)

using nauty’s geng function [18] to generate all connected $4$-regular graphs
on $n$ vertices for each $6\leq n\leq 10$;

  2. (2)

checking the diameter of the graphs generated in (1), and eliminating all with
diameter at least 3; then

  3. (3)

checking the graphs remaining after (2) for any unique shortest paths
connecting two vertices at distance $2$ and eliminating those graphs.

At the end of this computation we are left with a set of thirteen $4$-regular
graphs of diameter $2$ for which $q(G)=2$ is not ruled out. Figure 3 gives
these thirteen graphs. Lemma 3.2 completes the proof of Theorem 2.4 for graphs
with diameter at most $2$.

123456$R_{6,1}$1234567$R_{7,1}$7215346$R_{7,2}$51627384$R_{8,1}$12345678$R_{8,2}$12345678$R_{8,3}$12345678$R_{8,4}$12345678$R_{8,5}$12345678$R_{8,6}$123456789$R_{9,1}$123456789$R_{9,2}$123456789$R_{9,3}$12345678910$R_{10,1}$
Figure 3: Thirteen $4$-regular graphs with diameter $2$.

######  Lemma 3.2.

Table 1 lists all thirteen candidate $4$-regular graphs with diameter 2 (shown
in Figure 3) and includes their $q$-values (or a bound on their $q$-value).

Graph |  $q$-value
---|---
$R_{6,1}$ | 2
$R_{7,1}$ | 2
$R_{7,2}$ | 3
$R_{8,1}$ | 2
$R_{8,2}$ | 2

Graph |  $q$-value
---|---
$R_{8,3}$ | 2
$R_{8,4}$ | 2
$R_{8,5}$ | 2
$R_{8,6}$ | 2

Graph |  $q$-value
---|---
$R_{9,1}$ | $>2$
$R_{9,2}$ | $>2$
$R_{9,3}$ | 3
$R_{10,1}$ | 2

Table 1: The reduced list of thirteen $4$-regular graphs with diameter $2$.

###### Proof.

We treat each of the graphs in Table 1 separately, in the order they appear in
the table.

$R_{6,1}$: The graph $R_{6,1}$ is a closed candle, $R_{6,1}\cong H_{3}$. Thus
$q(R_{6,1})=2$ by Lemma 2.3.

$R_{7,1}$: The following matrix $M$ is a matrix in
$\mathcal{S}(R_{7,1}-\\{1,7\\})$ (the graph $R_{7,1}$ with the edge
$\\{1,7\\}$ deleted),

$M=\frac{1}{6}\left[\begin{array}[]{rrrrrrr}3&\sqrt{6}&-3&0&0&2\sqrt{3}&0\\\
\sqrt{6}&0&\sqrt{6}&2\sqrt{2}&0&0&-4\\\
-3&\sqrt{6}&-1&2\sqrt{3}&2\sqrt{2}&0&0\\\
0&2\sqrt{2}&2\sqrt{3}&-3&\sqrt{6}&1&0\\\
0&0&2\sqrt{2}&\sqrt{6}&-2&\sqrt{6}&2\sqrt{3}\\\
2\sqrt{3}&0&0&1&\sqrt{6}&-3&2\sqrt{2}\\\ 0&-4&0&0&2\sqrt{3}&2\sqrt{2}&0\\\
\end{array}\right].$

The matrix $M$ is orthogonal and has the Strong Spectral Property; see pages
10 and 11 in [7]. Thus $q(R_{7,1})=2$.

$R_{7,2}$: Note that $R_{7,2}$ can be constructed from $K_{4,3}$ by adding
edges $\\{1,2\\}$ and $\\{3,4\\}$. Suppose $M\in\mathcal{S}(R_{7,2})$. We
write $M$ as

$M=\left[\begin{array}[]{cc}C&B\\\ B^{T}&D\end{array}\right]$

where $C$ is a $4\times 4$ matrix, $B=[b_{1}\ b_{2}\ b_{3}]$ has no zero
entries, and $D=\operatorname{diag}(d_{1},d_{2},d_{3})$. Moreover,

$C=\left[\begin{array}[]{cc}C_{1}&0\\\ 0&C_{2}\end{array}\right]$

where each $C_{i}\in\mathcal{S}(K_{2})$.

Assume $M$ is an orthogonal matrix. Using Lemma 1.3, the columns of $B$ are
pairwise orthogonal and $Cb_{i}=-d_{i}b_{i}$ for $i=1,2,3.$ Partition each
$b_{i}$ into vectors $x_{i},y_{i}\in\mathbb{R}^{2}$. Now

$\left[\begin{array}[]{r}C_{1}x_{i}\\\
C_{2}y_{i}\end{array}\right]=\left[\begin{array}[]{cc}C_{1}&0\\\
0&C_{2}\end{array}\right]\left[\begin{array}[]{r}x_{i}\\\
y_{i}\end{array}\right]=Cb_{i}=\left[\begin{array}[]{r}-d_{i}x_{i}\\\
-d_{i}y_{i}\end{array}\right],$

so each $x_{i}$ is a $(-d_{i})$-eigenvector for $C_{1}$, and each $y_{i}$ is a
$(-d_{i})$-eigenvector for $C_{2}$.

The matrices $C_{1}$ and $C_{2}$ are each $2\times 2$ non-scalar symmetric
matrices, so each has two distinct eigenvalues. Thus, $d_{1},d_{2},d_{3}$
cannot be all distinct. Without loss of generality, suppose $d_{2}=d_{3}$. And
since the dimension of the $(-d_{2})$-eigenspace of $C_{i}$ is $1$, the
$(-d_{2})$-eigenvectors of $C_{i}$ are scalar multiples of each other. That
is, there exist $\alpha,\beta\neq 0$ so that $x_{3}=\alpha x_{2}$ and
$y_{3}=\beta y_{2}$.

Now we consider the $(2,2)$-block of $M^{2}$. We have

$\begin{array}[]{rcl}I_{3}-D^{2}&=&B^{T}B\\\
&=&\left[\begin{array}[]{rr}x_{1}^{T}&y_{1}^{T}\\\ x_{2}^{T}&y_{2}^{T}\\\
\alpha x_{2}^{T}&\beta
y_{2}^{T}\end{array}\right]\left[\begin{array}[]{rrr}x_{1}&x_{2}&\alpha
x_{2}\\\ y_{1}&y_{2}&\beta y_{2}\end{array}\right]\\\ \\\
&=&\left[\begin{array}[]{rrr}x_{1}^{T}x_{1}+y_{1}^{T}y_{1}&0&0\\\
0&x_{2}^{T}x_{2}+y_{2}^{T}y_{2}&0\\\
0&0&\alpha^{2}x_{2}^{T}x_{2}+\beta^{2}y_{2}^{T}y_{2}\end{array}\right].\end{array}$

From

$x_{2}^{T}x_{2}+y_{2}^{T}y_{2}=1-d_{2}^{2}=\alpha^{2}x_{2}^{T}x_{2}+\beta^{2}y_{2}^{T}y_{2}$

we conclude

$(\alpha^{2}-1)x_{2}^{T}x_{2}+(\beta^{2}-1)y_{2}^{T}y_{2}=0.$ (3.0.1)

Since the second and third columns of $B$ are orthogonal we also have

$\alpha x_{2}^{T}x_{2}+\beta y_{2}^{T}y_{2}=0,$

thus

$x_{2}^{T}x_{2}=-\displaystyle\frac{\beta}{\alpha}y_{2}^{T}y_{2}.$ (3.0.2)

Substituting (3.0.2) into (3.0.1) we obtain

$\displaystyle(\alpha^{2}-1)\left(-\displaystyle\frac{\beta}{\alpha}y_{2}^{T}y_{2}\right)+(\beta^{2}-1)y_{2}^{T}y_{2}=0$
$\displaystyle\Rightarrow$
$\displaystyle-\alpha^{2}\beta+\beta+\alpha\beta^{2}-\alpha=0$
$\displaystyle\Rightarrow$ $\displaystyle(\beta-\alpha)(\alpha\beta+1)=0$
$\displaystyle\Rightarrow$
$\displaystyle\beta=\alpha\quad\text{or}\quad\alpha\beta=-1.$

Since the columns of $B$ are orthogonal, $\alpha\neq\beta$. We show that
$\alpha\beta=-1$ leads to a contradiction which in turn implies that no
orthogonal $M\in\mathcal{S}(R_{7,2})$ exists. Hence, $q(R_{7,2})>2$. Suppose
$\alpha\beta=-1$; then

$\begin{array}[]{rcl}I_{4}-\left[\begin{array}[]{cc}C_{1}^{2}&0\\\
0&C_{2}^{2}\end{array}\right]&=&I_{4}-C^{2}\ =\ BB^{T}\ =\
\left[\begin{array}[]{rrr}x_{1}&x_{2}&\alpha x_{2}\\\ y_{1}&y_{2}&\beta
y_{2}\end{array}\right]\left[\begin{array}[]{rr}x_{1}^{T}&y_{1}^{T}\\\
x_{2}^{T}&y_{2}^{T}\\\ \alpha x_{2}^{T}&\beta y_{2}^{T}\end{array}\right]\\\
\\\
&=&\left[\begin{array}[]{rrr}x_{1}x_{1}^{T}+(1+\alpha^{2})x_{2}x_{2}^{T}&x_{1}y_{1}^{T}+(1+\alpha\beta)x_{2}y_{2}^{T}\\\
y_{1}x_{1}^{T}+(1+\alpha\beta)y_{2}x_{2}^{T}&y_{1}y_{1}^{T}+(1+\beta^{2})y_{2}y_{2}^{T}\end{array}\right]\\\
\\\
&=&\left[\begin{array}[]{rrr}x_{1}x_{1}^{T}+(1+\alpha^{2})x_{2}x_{2}^{T}&x_{1}y_{1}^{T}\\\
y_{1}x_{1}^{T}&y_{1}y_{1}^{T}+(1+\beta^{2})y_{2}y_{2}^{T}\end{array}\right].\end{array}$

So $x_{1}y_{1}^{T}=0$. This implies that either $x_{1}=0$ or $y_{1}=0$ which
is a contradiction since the entries of $B$ are nonzero.

To show $q(R_{7,2})=3$, we see that $R_{7,2}$ results from joined duplication
of a vertex of $G189$ in [3] or [8] (i.e., the graph obtained from $R_{7,2}$
by contracting edge $\\{3,4\\}$ is isomorphic to $G189$). From Table 3 in [8]
we find that $q(G189)=3$. Thus $q(R_{7,2})=3$.

$R_{8,1}$: The graph $R_{8,1}$ is a closed candle, $R_{8,1}\cong H_{4}$. Thus
$q(R_{8,1})=2$ by Lemma 2.3.

$R_{8,2}$: The following matrix $M_{8,2}$ is a matrix in
$\mathcal{S}(R_{8,2})$,

$M_{8,2}=\frac{1}{\sqrt{5}}\left[\begin{array}[]{rrrrrrrr}1&1&1&0&0&1&0&-1\\\
1&1&-1&0&-1&0&0&1\\\ 1&-1&0&\beta&0&0&\alpha&0\\\ 0&0&\beta&0&1&1&0&\alpha\\\
0&-1&0&1&-1&1&-1&0\\\ 1&0&0&1&1&-1&-1&0\\\ 0&0&\alpha&0&-1&-1&0&\beta\\\
-1&1&0&\alpha&0&0&\beta&0\end{array}\right],$

where $\alpha=(\sqrt{5}+1)/2$ and $\beta=(\sqrt{5}-1)/2$. Since $M_{8,2}$ is
orthogonal, $q(R_{8,2})=2$.

$R_{8,3}$: The following matrix $M_{8,3}$ is a matrix in
$\mathcal{S}(R_{8,3})$,

$M_{8,3}=\frac{1}{\sqrt{12}}\left[\begin{array}[]{rrrrrrrr}2&\sqrt{2}&0&-\sqrt{2}&\sqrt{2}&0&0&\sqrt{2}\\\
\sqrt{2}&0&\sqrt{2}&0&-2&-2&0&0\\\
0&\sqrt{2}&-2&\sqrt{2}&0&-\sqrt{2}&-\sqrt{2}&0\\\
-\sqrt{2}&0&\sqrt{2}&0&0&0&-2&2\\\ \sqrt{2}&-2&0&0&1&0&-2&-1\\\
0&-2&-\sqrt{2}&0&0&-1&1&2\\\ 0&0&-\sqrt{2}&-2&-2&1&-1&0\\\
\sqrt{2}&0&0&2&-1&2&0&1\end{array}\right].$

The matrix $M_{8,3}$ is orthogonal, so $q(R_{8,3})=2$.

$R_{8,4}$: Note that in our labelling of $R_{8,4}$, $N_{1}(7)=\\{1,3,6,8\\}$
and $N_{1}(8)=\\{1,3,6,7\\}$. Let $G$ be the graph obtained from $R_{8,4}$ by
contracting the edge $\\{7,8\\}$ to the vertex $(78)$ (and replacing every
pair of multiple edges by a single edge). The following matrix $M$ is a matrix
in $\mathcal{S}(G)$,

$M=\frac{1}{3}\left[\begin{array}[]{rrrrrrr}0&-\sqrt{3}&0&0&\sqrt{3}&0&\sqrt{3}\\\
-\sqrt{3}&1&-\sqrt{3}&1&1&0&0\\\ 0&-\sqrt{3}&0&\sqrt{3}&0&0&-\sqrt{3}\\\
0&1&\sqrt{3}&1&1&\sqrt{3}&0\\\ \sqrt{3}&1&0&1&1&-\sqrt{3}&0\\\
0&0&0&\sqrt{3}&-\sqrt{3}&0&\sqrt{3}\\\
\sqrt{3}&0&-\sqrt{3}&0&0&\sqrt{3}&0\end{array}\right]$

(here the vertices are ordered as $\\{1,2,3,4,5,6,(78)\\}$). The matrix $M$ is
orthogonal, so $q(G)=2$. Since $R_{8,4}$ is obtained from $G$ by joined
duplication of $(78)$, $q(R_{8,4})=2$.

$R_{8,5}$: Note that $R_{8,5}\cong K_{4}\Box K_{2}$. Thus by Corollary 6.8 in
[2], we have $q(R_{8,5})=2$.

$R_{8,6}$: The following matrix $M_{8,6}$ is a matrix in
$\mathcal{S}(R_{8,6})$,

$M_{8,6}=\frac{1}{\sqrt{10}}\left[\begin{array}[]{rrrrrrrr}-\sqrt{2}&\sqrt{2}&-1&0&0&0&-1&-2\\\
\sqrt{2}&\sqrt{2}&-2&1&0&0&0&1\\\ -1&-2&-\sqrt{2}&\sqrt{2}&1&0&0&0\\\
0&1&\sqrt{2}&\sqrt{2}&2&-1&0&0\\\ 0&0&1&2&-\sqrt{2}&\sqrt{2}&-1&0\\\
0&0&0&-1&\sqrt{2}&\sqrt{2}&-2&1\\\ -1&0&0&0&-1&-2&-\sqrt{2}&\sqrt{2}\\\
-2&1&0&0&0&1&\sqrt{2}&\sqrt{2}\end{array}\right].$

The matrix $M_{8,6}$ is orthogonal, so $q(R_{8,6})=2$.

$R_{9,1}$: Consider a matrix $M\in\mathcal{S}(R_{9,1})$ where we use variables
for each edge and vertex. That is,

$[M]_{ij}=\begin{cases}x_{ij}&\text{if $ij\in E(R_{9,1})$,}\\\ x_{ii}&\text{if
$i=j$, and}\\\ 0&\text{if $ij\notin E(R_{9,1})$.}\end{cases}$

Suppose $M$ is an orthogonal matrix. Note that the edges of $R_{9,1}$ can be
partitioned into the $9$-cycle $(1,2,3,4,5,6,7,8,9,1)$, and the $3$-cycles
$(1,4,7,1)$, $(2,5,8,2)$, and $(3,6,9,3)$. Since the edge $\\{1,2\\}$ does not
lie in any triangle in $R_{9,1}$, we have

$0=[M^{2}]_{12}=x_{11}x_{12}+x_{12}x_{22}.$

Since $x_{12}\neq 0$, we conclude that $x_{22}=-x_{11}$. Repeating this
argument for each edge of the $9$-cycle, we see that $x_{ii}=-x_{ii}$, or
$x_{ii}=0$ for all $1\leq i\leq 9$.

Now consider the $3$-cycle $(1,4,7,1)$. Taking account of the walks of length
$2$ between $1$ and $7$, we have

$0=[M^{2}]_{17}=x_{11}x_{17}+x_{17}x_{77}+x_{14}x_{47}=x_{14}x_{47}.$

But since $x_{14},x_{47}\neq 0$, this is impossible. Thus there is no
orthogonal matrix $M\in\mathcal{S}(R_{9,1})$, and we conclude $q(R_{9,1})>2$.

$R_{9,2}$: Consider a matrix $M\in\mathcal{S}(R_{9,2})$ where we use variables
for each edge and vertex. That is,

$[M]_{ij}=\begin{cases}x_{ij}&\text{if $ij\in E(R_{9,2})$,}\\\ x_{ii}&\text{if
$i=j$, and}\\\ 0&\text{if $ij\notin E(R_{9,2})$.}\end{cases}$

Suppose $M$ is an orthogonal matrix. Note that $\\{6,7\\}\in E(R_{9,2})$, but
$\\{6,7\\}$ is not included in any $3$-cycle in $R_{9,2}$. Thus

$0=[M^{2}]_{67}=x_{66}x_{67}+x_{67}x_{77}.$

Since the variable $x_{67}\neq 0$, this implies that $x_{66}=-x_{77}$.
Similarly, we see that edges $\\{2,6\\}$ and $\\{3,7\\}$ are not included in
any $3$-cycles in $R_{9,2}$. Considering $[M^{2}]_{26}$ and $[M^{2}]_{37}$ we
derive $x_{22}=-x_{66}$ and $x_{33}=-x_{77}$. Combining these three equations,
we have $x_{22}=-x_{33}$. Now consider the paths of length $2$ between
vertices $2$ and $3$. We have

$0=[M^{2}]_{23}=x_{22}x_{23}+x_{23}x_{33}+x_{12}x_{13}=x_{12}x_{13}.$

But since $x_{12},x_{13}\neq 0$, this is impossible. Thus there is no
orthogonal matrix $M\in\mathcal{S}(R_{9,2})$, and we conclude $q(R_{9,2})>2$.

$R_{9,3}$: Note that $\\{1,2,3\\}$, $\\{4,5,9\\}$, and $\\{6,7,8\\}$ all
induce $K_{3}$ subgraphs in $R_{9,3}$. Moreover, $\\{1,8,9\\}$, $\\{2,5,6\\}$,
and $\\{3,4,7\\}$ also induce $K_{3}$ subgraphs in $R_{9,3}$, and we see that
$R_{9,3}\cong K_{3}\Box K_{3}$. We prove in Lemma 3.3 that $q(K_{m}\Box
K_{n})=3$ for all $m,n\geq 3$. This establishes $q(R_{9,3})=3$.

$R_{10,1}$: The graph $R_{10,1}$ is a closed candle, $R_{10,1}\cong H_{5}$.
Thus $q(R_{10,1})=2$ by Lemma 2.3. ∎

In order to complete the preceding proof, we establish the following lemma,
which shows that the bound in Proposition 3.1 of [8] is sharp for complete
graphs.

######  Lemma 3.3.

For $m,n\geq 3$, we have $q(K_{m}\Box K_{n})=3.$

###### Proof.

Since $q(K_{s})=2$ for any $s\geq 2$ it follows from a basic application of
Kronecker products that $q(K_{m}\Box K_{n})\leq 3$ (this inequality can also
be deduced from Proposition 3.1 in [8]). It remains to verify that in fact
$q(K_{m}\Box K_{n})\geq 3$.

If $q(K_{m}\Box K_{n})=2,$ then there exists a matrix
$C\in\mathcal{S}(K_{m}\Box K_{n})$ that satisfies $C^{2}=I$ and is given by

$C=\left[\begin{array}[]{ccccc}A_{11}&D_{12}&D_{13}&\ldots&D_{1m}\\\
D_{12}&A_{22}&D_{23}&\ldots&D_{2m}\\\ &&\ddots\\\
D_{1m}&D_{2m}&D_{3m}&\ldots&A_{mm}\\\ \end{array}\right],$

where $D_{ij}$ is an $n\times n$ diagonal matrix with nonzero diagonal entries
for each $1\leq i,j\leq m$ and $A_{ii}\in\mathcal{S}(K_{n})$ for $1\leq i\leq
m$.

Let $[C^{2}]_{ij}$ denote the $(i,j)$ block of the matrix $C^{2}$ partitioned
conformally with $C$ above. Then

$\displaystyle[C^{2}]_{12}$
$\displaystyle=A_{11}D_{12}+D_{12}A_{22}+\sum_{j=3}^{m}{D_{1j}}D_{{2j}}=0,$
$\displaystyle[C^{2}]_{13}$
$\displaystyle=A_{11}D_{13}+D_{13}A_{33}+\sum_{j\neq 1,3}{D_{1j}}D_{{3j}}=0,$
$\displaystyle[C^{2}]_{23}$
$\displaystyle=A_{22}D_{23}+D_{23}A_{33}+\sum_{j\neq 2,3}{D_{2j}}D_{{3j}}=0.$

Since $D_{ij}$ is invertible, we have

$\displaystyle A_{22}$
$\displaystyle=-D_{12}^{-1}A_{11}D_{12}-D_{12}^{-1}\left(\sum_{j=3}^{m}{D_{1j}}D_{{2j}}\right),$
(3.0.3) $\displaystyle A_{33}$
$\displaystyle=-D_{13}^{-1}A_{11}D_{13}-D_{13}^{-1}\left(\sum_{j\neq
1,3}{D_{1j}}D_{{3j}}\right),$ (3.0.4) $\displaystyle A_{22}$
$\displaystyle=-D_{23}A_{33}D_{23}^{-1}-\left(\sum_{j\neq
2,3}{D_{2j}}D_{{3j}}\right)D_{23}^{-1}.$ (3.0.5)

From (3.0.4) and (3.0.5) we have

$A_{22}=D_{23}D_{13}^{-1}A_{11}D_{13}D_{23}^{-1}+D_{23}D_{13}^{-1}\left(\sum_{j\neq
1,3}{D_{1j}}D_{{3j}}\right)D_{23}^{-1}-\left(\sum_{j\neq
2,3}{D_{2j}}D_{{3j}}\right)D_{23}^{-1}.$ (3.0.6)

Note that $[D_{12}]_{ij}=c_{i(n+j)}$, $[D_{13}]_{ij}=c_{i(2n+j)},$ and
$[D_{23}]_{ij}=c_{(n+i)(2n+j)}$, and, by assumption, each such entry is
nonzero when $i=j$. By direct calculation we have

$[D_{23}D_{13}^{-1}A_{11}D_{13}D_{23}^{-1}]_{ij}=\displaystyle\frac{c_{ij}c_{(n+i)(2n+i)}c_{j(2n+j)}}{c_{i(2n+i)}c_{(n+j)(2n+j)}}$

and

$[D_{12}^{-1}A_{11}D_{12}]_{ij}=\displaystyle\frac{c_{ij}c_{j(n+j)}}{c_{i(n+i)}}.$

Using (3.0.3) and (3.0.6), and letting $(i,j)=(1,2),(1,3),$ and $(2,3)$ (there
are no contributions from the diagonal terms in (3.0.3) nor (3.0.6)) we have

$\displaystyle\displaystyle\frac{c_{12}c_{(n+1)(2n+1)}c_{2(2n+2)}}{c_{1(2n+1)}c_{(n+2)(2n+2)}}$
$\displaystyle=-\displaystyle\frac{c_{12}c_{2(n+2)}}{c_{1(n+1)}}$ (3.0.7)
$\displaystyle\displaystyle\frac{c_{13}c_{(n+1)(2n+1)}c_{3(2n+3)}}{c_{1(2n+1)}c_{(n+3)(2n+3)}}$
$\displaystyle=-\displaystyle\frac{c_{13}c_{3(n+3)}}{c_{1(n+1)}}$ (3.0.8)
$\displaystyle\displaystyle\frac{c_{23}c_{(n+2)(2n+2)}c_{3(2n+3)}}{c_{2(2n+2)}c_{(n+3)(2n+3)}}$
$\displaystyle=-\displaystyle\frac{c_{23}c_{3(n+3)}}{c_{2(n+2)}}.$ (3.0.9)

Manipulating equations (3.0.7) and (3.0.8) produces the equation

$\displaystyle\displaystyle\frac{c_{2(2n+2)}c_{(n+3)(2n+3)}}{c_{(n+2)(2n+2)}c_{3(2n+3)}}$
$\displaystyle=$ $\displaystyle\displaystyle\frac{c_{2(n+2)}}{c_{3(n+3)}}$

or

$\displaystyle c_{3(n+3)}c_{2(2n+2)}c_{(n+3)(2n+3)}$ $\displaystyle=$
$\displaystyle c_{(n+2)(2n+2)}c_{3(2n+3)}c_{2(n+2)}.$

However from (3.0.9) we have

$\displaystyle
c_{(n+2)(2n+2)}c_{3(2n+3)}c_{2(n+2)}=-c_{2(2n+2)}c_{(n+3)(2n+3)}c_{3(n+3)}.$

which is a contradiction. ∎

This completes the verification of the $q$-values listed in Table 1, which
completes the proof of Theorem 2.4 for graphs with diameter at most $2$.

##  4 Sporadic 4-Regular Graphs and Theorem 2.4

In this section we establish whether or not $q(G)=2$ for a collection of
sporadic graphs. These graphs are all connected with diameter at least $3$ and
arise within the proofs in Section 5.

######  Lemma 4.1.

Table 2 lists candidate $4$-regular graphs with diameter at least 3 (also
shown in Figure 4) and includes their $q$-values (or a bound on their
$q$-value).

Graph |  $q$-value
---|---
$R_{10,2}$ | 2
$R_{10,3}$ | 2
$R_{10,4}$ | 2
$R_{12,1}$ | $>2$

Graph |  $q$-value
---|---
$R_{12,2}$ | $>2$
$R_{12,3}$ | 2
$R_{14,1}$ | 2

Table 2: Sporadic $4$-Regular Graphs with diameter at least 3.

12345678910$R_{10,2}$12345678910$R_{10,3}$12345678910$R_{10,4}$123456789101112$R_{12,1}$123456789101112$R_{12,2}$178910234561112$R_{12,3}$1234567891011121314$R_{14,1}$
Figure 4: Sporadic $4$-regular graphs with diameter at least 3.

###### Proof.

$R_{10,2}$: To see that $q(R_{10,2})=2$, note that the following matrix
$M_{10,2}\in R_{10,2}$ is orthogonal,

$M_{10,2}=\frac{1}{4}\left[\begin{array}[]{rrrrrrrrrr}-\sqrt{2}&-2&0&0&\sqrt{2}&0&0&2&0&-2\\\
-2&\sqrt{2}&2&0&0&\sqrt{2}&0&0&-2&0\\\ 0&2&-\sqrt{2}&-2&0&0&\sqrt{2}&0&0&-2\\\
0&0&-2&\sqrt{2}&2&0&0&-\sqrt{2}&-2&0\\\ \sqrt{2}&0&0&2&-\sqrt{2}&2&0&0&0&-2\\\
0&\sqrt{2}&0&0&2&\sqrt{2}&-2&0&2&0\\\ 0&0&\sqrt{2}&0&0&-2&-\sqrt{2}&-2&0&-2\\\
2&0&0&-\sqrt{2}&0&0&-2&\sqrt{2}&-2&0\\\ 0&-2&0&-2&0&2&0&-2&0&0\\\
-2&0&-2&0&-2&0&-2&0&0&0\end{array}\right].$

$R_{10,3}$: Note that contracting edges $\\{1,2\\}$ and $\\{6,7\\}$ in
$R_{10,3}$ gives a graph isomorphic to $Q_{3}$. Since $R_{10,3}$ can be
obtained from $Q_{3}$ by joined duplicating a pair of antipodal vertices,
Corollary 3.3 from [3] implies that $q(R_{10,3})\leq q(Q_{3})=2$. Thus
$q(R_{10,3})=2$.

$R_{10,4}$: Theorem 5.3 in [4] shows that $K_{n,n}$ with a perfect matching
deleted has $q$-value 2 for all $n\neq 1,3$. Since $R_{10,4}$ is isomorphic to
$K_{5,5}$ with a perfect matching deleted, $q(R_{10,4})=2$.

$R_{12,1}$: Following the example after Lemma 1.3, set
$V_{1}=\\{1,3,5,7,10,12\\}$ and $V_{2}=\\{2,4,6,8,9,11\\}$. Assume that there
exists an $M\in S(R_{12,1})$ with $M^{2}=I$ and $M$ is of the form

$M=\left[\begin{array}[]{cc}C&B\\\ B^{T}&D\end{array}\right],$

where $C$ and $D$ are diagonal matrices. Then by Lemma 1.3 we know that $B$
must be an orthogonal matrix. Consider the last two rows of $B$ (whose nonzero
patterns are the same since vertices 10 and 12 have the same neighbors) and
suppose they are equal to $u=[a,b,c,d,0,0]$ and $v=[x,y,z,w,0,0]$. Since both
$u$ and $v$ are orthogonal to row 4 of $B$ we may deduce that
$[z,w]=\alpha[c,d]$ for some nonzero scalar $\alpha$. Similarly since both $u$
and $v$ are orthogonal to row 2 and to row 3 we conclude that
$[y,z]=\beta[b,c]$ and $[x,y]=\gamma[a,b]$, where $\beta$ and $\gamma$ are
nonzero. Now it follows that $\alpha=\beta=\gamma$ and hence row 5 is a
multiple of row 6 which contradicts the assumption that $B$ is orthogonal.
Hence $q(R_{12,1})>2$.

$R_{12,2}$: Using a similar set up as in the case of $R_{12,1}$ set
$V_{1}=\\{2,3,4,5,11,12\\}$ and $V_{2}=\\{1,6,7,8,9,10\\}$. Assume that there
exists an $M\in S(R_{12,1})$ with $M^{2}=I$ and $M$ is of the form

$M=\left[\begin{array}[]{cc}C&B\\\ B^{T}&D\end{array}\right],$

where $C$ and $D$ are diagonal matrices. Then by Lemma 1.3 we know that $B$
must be an orthogonal matrix. Consider rows 2 and 3 of $B$ (whose nonzero
patterns are the same since vertices 3 and 4 have the same neighbors).
Following a similar argument as used for the graph $R_{12,1}$ (both rows 2 and
3 must be orthogonal to rows 1,5, and 6) we can deduce that rows 2 and 3 must
be multiples of one another which is a contradiction. Hence $q(R_{12,2})>2$.

$R_{12,3}$: To see that $q(R_{12,3})=2$, we present an orthogonal matrix
$M_{12,3}\in\mathcal{S}(R_{12,3})$ in block form, as above. We take
$V_{1}=\\{1,2,3,4,5,6\\}$ and $V_{2}=\\{7,8,9,10,11,12\\}$. Let

$B_{12,3}=\left[\begin{array}[]{rrrrrr}-\zeta&-\beta&\zeta&-\sqrt{5}/5&0&0\\\
\varepsilon&-\gamma&\beta&0&\delta&0\\\ \sqrt{5}/5&0&0&-\zeta&-\beta&-\zeta\\\
\sqrt{5}/5&0&\sqrt{5}/5&0&-\varepsilon&\zeta\\\
0&\delta&0&-\varepsilon&\gamma&\beta\\\
0&-\varepsilon&-\zeta&-\sqrt{5}/5&0&\sqrt{5}/5\\\ \end{array}\right],$

where

$\alpha=(\sqrt{5}+1)/2,\ \ \ \beta=\sqrt{2\sqrt{5}/5-4/5},\ \ \
\gamma=\sqrt{-7\sqrt{5}/10+17/10},\ \ \ \delta=\sqrt{5}/10+1/2,$
$\varepsilon=\alpha\beta,\ \ \text{and}\ \ \zeta=\alpha\gamma.\\\ $

Thus

$M_{12,3}=\left[\begin{array}[]{cc}0&B_{12,3}\\\
B_{12,3}^{T}&0\end{array}\right]$

has the desired properties.

$R_{14,1}$: To see that $q(R_{14,1})=2$, we provide an orthogonal matrix
$M_{14,1}\in\mathcal{S}(R_{14,1})$ in block form. We take
$V_{1}=\\{1,2,3,4,5,6,7\\}$ and $V_{2}=\\{8,9,10,11,12,13,14\\}$, and let

$B_{14,1}=\frac{1}{2}\left[\begin{array}[]{rrrrrrr}1&0&1&0&0&-1&1\\\
1&1&0&1&0&0&-1\\\ -1&1&1&0&1&0&0\\\ 0&-1&1&1&0&1&0\\\ 0&0&-1&1&1&0&1\\\
1&0&0&-1&1&1&0\\\ 0&1&0&0&-1&1&1\\\ \end{array}\right].$

Then

$M_{14,1}=\left[\begin{array}[]{cc}0&B_{14,1}\\\
B_{14,1}^{T}&0\end{array}\right]$

has the desired properties. We note that $M_{14,1}$ was presented in [19].

∎

##  5 Proof of Theorem 2.4 for 4-Regular Graphs with Large Diameter

In this section we complete the proof of items (3), (4) and (5) of Theorem 2.4
for graphs with diameter at least $3$. Recall from Section 1.1, in the
distance partition from any vertex $v$, every $u\in N_{i}(v)$ has at least two
neighbors in $N_{i-1}(v)$ for all $i\geq 2$. These edges account for
$2n-2-\deg(v)=2n-6$ of the edges of $G$. We consider the possible locations of
the six extra edges not accounted for by these predecessors. Throughout the
proofs in this section, once all of the edges incident with a vertex have been
accounted for, we say that the vertex is _full_.

######  Lemma 5.1.

Let $G$ be a connected $4$-regular graph with diameter at least $3$ and let
$v$ be a vertex for which $\epsilon(v)\geq 3$. Suppose that every vertex in
$N_{2}(v)$ and $N_{3}(v)$ has exactly two predecessors and that
$G[N_{1}(v)]\cup G[N_{2}(v)]$ contains at most three edges. Then $q(G)>2$.

###### Proof.

Assume $q(G)=2$.

Case 1: $N_{1}(v)$ is an independent set.

Each pair of vertices of $N_{1}(v)$ share $v$ as a common neighbor, so each
pair must share a common neighbor in $N_{2}(v)$ as well. There are
$\binom{4}{2}=6$ such pairings, each resulting in a distinct vertex in
$N_{2}(v)$ with two predecessors in $N_{1}(v)$ and accounting for all the
edges between $N_{1}(v)$ and $N_{2}(v)$, also implying that $|N_{2}(v)|=6$.

Suppose each vertex in $N_{2}(v)$ has a neighbor in $N_{2}(v)$. Then there are
three edges in $G[N_{2}(v)]$ and $G[N_{2}(v)]=3K_{2}$. Let $xy$ be an edge in
$N_{2}(v)$ and let $a,b$ be the predecessors of $x$. Then $a,b$ are not both
predecessors of $y$. Suppose that $b$ and $y$ are not adjacent. Then $bxy$ is
a unique shortest path of length 2 between $b$ and $y$.

Otherwise some vertex, say $u\in N_{2}(v)$, has no neighbor in $N_{2}(v)$.
Vertex $u$ shares a common neighbor in $N_{1}(v)$ with four other vertices in
$N_{2}(v)$, call them $x_{1},x_{2},x_{3},x_{4}$. To avoid unique paths from
$u$ to $x_{i}$ for $i=1,2,3,4$, $u$ and $x_{i}$ must have a common successor.
These common successors are distinct since each has just 2 predecessors. But
then $\deg(u)\geq 6$.

Case 2: $G[N_{1}(v)]$ contains exactly one edge.

This case follows the same logic as Case 1, with the exception that there are
five pairings of nonadjacent vertices in $N_{1}(v)$ that share $v$ as a common
neighbor so each of these pairs must have a common neighbor in $N_{2}(v)$. As
before, this accounts for all the edges between $N_{1}(v)$ and $N_{2}(v)$, so
there are exactly five vertices in $N_{2}(v)$. Since $G[N_{2}(v)]$ contains at
most two edges, some vertex $u$ in $N_{2}(v)$ has no neighbors in $N_{2}(v)$.
Vertex $u$ shares a neighbor in $N_{1}(v)$ with at least three other vertices
in $N_{2}(v)$ . Arguing similarly to Case 1, $\deg(u)\geq 5$.

Case 3: $G[N_{1}(v)]$ contains exactly two edges.

Suppose the two edges do not share a vertex. Then the four pairs of
nonadjacent vertices in $N_{1}(v)$ that have $v$ as a common neighbor must
each have a common neighbor in $N_{2}(v)$, accounting for all the edges
between $N_{1}(v)$ and $N_{2}(v)$ and resulting in exactly four vertices in
$N_{2}(v)$. Since there is at most one edge in $N_{2}(v)$, there is a vertex
$u$ in $N_{2}(v)$ that has no neighbor in $N_{2}(v)$. Let $a$ be a neighbor of
$u$ in $N_{1}(v)$ with $ab$ one of the two edges in $G[N_{1}(v)]$. Then $uab$
is a unique shortest path of length $2$ in $G$.

Otherwise the two edges in $G[N_{1}(v)]$ share a vertex, say $c$. Then $c$ has
exactly one neighbor $w$ in $N_{2}(v)$. Let the non-neighbor of $c$ in
$N_{1}(v)$ be $d$. Since $c$ and $d$ have $v$ as a common neighbor, the other
predecessor of $w$ in $N_{1}(v)$ must be $d$. To prevent a unique shortest
path of length 2 between $w$ and the neighbors of $c$ in $N_{1}(v)$, there
must be an edge connecting $w$ to a vertex, $y\in N_{2}(v)$ whose two
predecessors are the two neighbors of $c$ in $N_{1}(v)$. But this creates a
unique shortest path $dwy$ of length $2$. Note that in this case we did not
use the hypothesis that each vertex in $N_{3}(v)$ has two predecessors. This
will be used later in the proof of Lemma 5.3.

Case 4: $G[N_{1}(v)]$ contains exactly three edges.

If $G[N_{1}(v)]\cong P_{4}$, then the two endpoints of the $P_{4}$ must have a
common neighbor $w$ in $N_{2}(v)$. Then $w$ has a unique shortest path of
length 2 to both non-end vertices of $P_{4}$.

If $G[N_{1}(v)]\cong C_{3}\cup K_{1}$, the same argument as in Case 3 applies,
with $c$ being any vertex in the $C_{3}$. Note again, that in these first two
possibilities that the hypothesis that each vertex in $N_{3}(v)$ has two
predecessors was not used. This will be used at the end of the proof of Lemma
5.3.

Suppose $G[N_{1}(v)]\cong K_{1,3}$. Then each pair of nonadjacent vertices in
$N_{1}(v)$ has a common neighbor in $N_{1}(v)$, in addition to the common
neighbor $v$. But in order for each vertex in $N_{1}(v)$ to have degree 4,
there must be three vertices in $N_{2}(v)$, each adjacent to a different pair
of leaves of the $K_{1,3}$. Each pair of vertices in $N_{2}(v)$ has one common
neighbor in $N_{1}(v)$, and since $N_{2}(v)$ is an independent set, this
implies that each pair of vertices in $N_{2}(v)$ must have a common neighbor
in $N_{3}(v)$. These neighbors are distinct because each vertex in $N_{3}(v)$
has two predecessors. Note that all three vertices in $N_{2}(v)$ are full. Let
$a$ be a leaf vertex of the $K_{1,3}$; then there exist two paths of length 2,
$asx$ and $aty$ for some $s,t\in N_{2}(v)$ and $x,y\in N_{3}(v)$, that are the
unique $ax$ and $ay$ paths of length 2. ∎

######  Corollary 5.2.

Let $G$ be a connected $4$-regular graph with diameter at least $3$. If $v$ is
a vertex with $\epsilon(v)\geq 3$ and for which there is no vertex in the
distance partition from $v$ with 3 or 4 predecessors, then $q(G)>2$.

###### Proof.

Let $N_{d}(v)$ be the furthest distance set of $v$. Since every vertex in
$N_{d}(v)$ has exactly two predecessors, we know that $G[N_{d}(v)]$ is
$2$-regular. So at least three of the six extra edges must be in $N_{d}(v)$,
and the maximum number of edges that could appear within the subgraphs
$G[N_{i}(v)]$ for $1\leq i\leq d-1$ is three. So the hypotheses of Lemma 5.1
are satisfied and $q(G)>2$. ∎

######  Lemma 5.3.

Let $G$ be a connected $4$-regular graph with diameter at least $3$ and let
$v$ be a vertex for which $\epsilon(v)\geq 3$. If in the distance partition
from $v$ no vertex has four predecessors, then either $G\cong R_{10,3}$,
$G\cong K_{3}\Box C_{4}$, or $q(G)>2$.

###### Proof.

Suppose $q(G)=2$. We assume $G$ has a vertex with three predecessors as
otherwise the result follows from Corollary 5.2. We begin by establishing
three claims.

_Claim #1:_ Any vertex with three predecessors cannot have a successor.

_Proof of Claim #1:_ Suppose some vertex $w$ in $N_{i}(v)$ has three
predecessors in $N_{i-1}(v)$ and one successor $z$ in $N_{i+1}(v)$. Note that
$i$ must be at least $2$. Since $z$ has at most three predecessors in
$N_{i}(v)$, there must be a neighbor $x$ of $z$ in $N_{i+1}(v)$ or
$N_{i+2}(v)$. But then there is a unique shortest path of length 2 between $w$
and $x$, as $w$ is full.

Observe that the proof of Claim #1 also implies that if $G$ is a graph and
$v\in V(G)$ for which some vertex in the distance partition from $v$ has four
predecessors, any vertex $w\in N_{i}(v)$ with three predecessors cannot have a
successor $z$ unless $z$ is a vertex with four predecessors. We will use this
in Case 4 of the proof of Lemma 5.4.

_Claim #2:_ Vertices with three predecessors occur in pairs, with each pair
the endpoints of a path in some distance set $N_{i}(v)$.

_Proof of Claim #2:_ Suppose $w_{1}\in N_{i}(v)$ has three predecessors. Since
it can have no successors but has degree 4, it must have a neighbor $w_{2}\in
N_{i}(v)$. So $w_{1}$ is one end of a path $w_{1}w_{2}\ldots w_{k}$ in
$N_{i}(v)$, where $w_{2},\ldots,w_{k-1}$ have two predecessors each, and hence
is full, and $w_{k-1}$ is the only neighbor of $w_{k}$ in $N_{i}(v)$. If
$w_{k}$ has a successor $y$, then $yw_{k}w_{k-1}$ is a unique shortest path of
length 2 between $y$ and $w_{k-1}$. So $w_{k}$ must have three predecessors.

_Claim #3:_ A pair of vertices with three predecessors can occur only in
$N_{i}(v)$ for $i\geq 3$.

_Proof of Claim #3:_ Let $w$ be a vertex with three predecessors. Suppose
$w\in N_{2}(v)$. Note that $w$ cannot have a successor. Let $z$ be another
vertex in $N_{2}(v)$ with three predecessors, and no successor. Then there are
at least two vertices in $N_{1}(v)$ that are common predecessors of $w$ and
$z$. Since $\epsilon(v)\geq 3$, there must be a vertex $x\in N_{2}(v)$ that
has a successor $y\in N_{3}(v)$. So $x$ cannot have three predecessors and
therefore must have two. If a predecessor of $x$ is a common predecessor of
$w$ and $z$, then there is a unique shortest path of length 2 between $y$ and
this predecessor of $x$. So $w$ and $z$ must have exactly two shared
predecessors, and the two predecessors of $x$ each has exactly one of
$\\{w,z\\}$ as a successor. This implies that, via $N_{1}(v)$, there is a path
of length 2 between $x$ and $w$ (and between $x$ and $z$). Since these paths
cannot be unique shortest paths, and $x$ cannot be adjacent to $w$ (as it
would then be on the $wz$ path in $N_{2}(v)$, and hence have degree at least
$5$), $x$ must have a common neighbor $t\neq z$ in $N_{2}(v)$ with $w$. But
then $yxt$ is a unique shortest path of length 2 between $y$ and $t$.

Let $S$ represent the set of vertices with three predecessors. We have shown
that no vertex in $S$ can have a successor and all vertices in $S$ must occur
in pairs in the distance sets $N_{i}(v)$ for $i\geq 3$. A pair of such
vertices requires a minimum of three of the six additional edges. It follows
that $|S|=2$ or $|S|=4$, leaving at most three or zero edges that could appear
in the subgraphs $G[N_{i}(v)]$ for $1\leq i\leq\epsilon(v)-1$, respectively.
Let $j$ represent the smallest value of $i$ for which $N_{i}(v)$ contains an
element of $S$. If $j>3$, then Lemma 5.1 implies that $q(G)>2$, so we only
have to consider $j=3$.

Case 1: $N_{1}(v)$ is an independent set.

By the argument in Case 1 of Lemma 5.1, $N_{2}(v)$ consists of six vertices,
such that each vertex shares one common neighbor in $N_{1}(v)$ with each of
four other vertices in $N_{2}(v)$. Consider $u\in N_{2}(v)$, and denote by $w$
the unique vertex in $N_{2}(v)$ with which $u$ does not share a neighbor in
$N_{1}(v)$.

Case 1(a): $N_{2}(v)$ is also an independent set.

Let $y_{1},y_{2}$ be the successors of $u$ in $N_{3}(v)$ and let
$x_{1},x_{2},x_{3},x_{4}$ be the vertices in $N_{2}(v)$ that share a unique
common predecessor with $u$. Since there cannot be a unique shortest path of
length 2 between $u$ and $x_{i}$ for any $i$, each $x_{i}$ must be adjacent to
$y_{1}$ or $y_{2}$. Since neither $y_{1}$ nor $y_{2}$ has four predecessors,
$y_{1}$ must be adjacent to two of the $x_{i}$ and $y_{2}$ to the other two.
Then $y_{1},y_{2}\in S$. Neither $y_{1}$ nor $y_{2}$ is adjacent to $w$, so
repeating the same argument, there are successors $z_{1},z_{2}\in S$ of $w$
such that $z_{1}$ is adjacent to two of the $x_{i}$ and $z_{2}$ to the other
two. This accounts for all edges between $N_{2}(v)$ and $N_{3}(v)$, so
$N_{3}(v)=\\{y_{1},y_{2},z_{1},z_{2}\\}=S$. Note that each $x_{i}$ is adjacent
to exactly one of $y_{1},y_{2}$ and one of $z_{1},z_{2}$. Since none of
$y_{1},y_{2},z_{1},z_{2}$ has a successor by Claim #1, there are exactly two
edges in $G[N_{3}(v)]$ that do not share an endpoint. If $y_{1}y_{2}$ is not
an edge, then $y_{1}uy_{2}$ is the unique shortest path of length 2. So
$y_{1}y_{2}$ is an edge, and $z_{1}z_{2}$ is an edge. Without loss of
generality, suppose that $x_{1}$ is adjacent to $y_{1}$. Then $x_{1}$ and
$y_{2}$ are not adjacent and $x_{1}y_{1}y_{2}$ is a unique shortest path of
length 2.

Case 1(b): $N_{2}(v)$ is not independent, so $|S|=2$.

Suppose there is an edge $ut$ in $G[N_{2}(v)]$, not sharing an endpoint with
any other edge in $G[N_{2}(v)]$. Then there is a shortest path of length 2
through $N_{1}(v)$ from $u$ to at least three other vertices in $N_{2}(v)$. So
for each of these three vertices there must be a shortest path of length 2
through $N_{3}(v)$. Since $\deg(u)=4$, $u$ can only have one successor, so
there is a single vertex $x\in N_{3}(v)$ on all three paths. But then $x$ has
four predecessors.

Now suppose $ut$ and $rt$ are edges in $G[N_{2}(v)]$. Recall that $w$ is the
vertex in $N_{2}(v)$ that shares no predecessors with $u$. Let $y$ and $z$ be
the remaining vertices in $N_{2}(v)$. To avoid a unique shortest path of
length 2 through $N_{1}(v)$ from $u$ to $y$ or $z$, there must be a vertex $x$
in $N_{3}(v)$ whose predecessors are $u$, $y$, and $z$. Then $tux$ is a unique
shortest path of length 2.

Therefore Case 1 cannot occur, and $N_{1}(v)$ is never an independent set.

Case 2: $G[N_{1}(v)]$ contains exactly one edge, so $|S|=2$.

We follow the proof of Case 2 of Lemma 5.1 but make more careful note of the
location of the edges in $N_{2}(v)$. Let $a$ and $b$ represent the adjacent
vertices in $N_{1}(v)$. Let $u$ be the vertex in $N_{2}(v)$ whose two
predecessors are $N_{1}(v)\setminus\\{a,b\\}$. Each of the four vertices in
$N_{2}(v)\setminus\\{u\\}$ has exactly one of $a$ or $b$ as a predecessor.
Note that there are four shortest paths of length 2 between these vertices and
the other vertex in $\\{a,b\\}$. Since these paths cannot be unique, there
must be two independent edges in $N_{2}(v)$ that connect vertices with no
common predecessor in $\\{a,b\\}$. Note that if two adjacent vertices in
$N_{2}(v)$ do not share a predecessor in $N_{1}(v)\setminus\\{a,b\\}$, then
there are unique shortest paths of length 2 between the vertices
$N_{1}(v)\setminus\\{a,b\\}$ and the neighbors of their successors in
$N_{2}(v)$. So the independent edges between the vertices of
$N_{2}(v)\setminus\\{u\\}$ connect vertices so that each pair has one common
predecessor in $N_{1}(v)\setminus\\{a,b\\}$ and has one non-common predecessor
in $\\{a,b\\}$.

Each endpoint of the independent edges in $N_{2}(v)$ has exactly one
successor, and $u$ must have two successors. It follows that there are six
edges between the vertices in $N_{2}(v)$ and the vertices in $N_{3}(v)$. Since
the two vertices in $S\cap N_{3}(v)$ each have three predecessors, there can
be no other vertices in $N_{3}(v)$ and $S=N_{3}(v)$. From Claim #1, these two
vertices must be adjacent to each other. Each of the four vertices in
$N_{2}(v)\setminus\\{u\\}$ are adjacent to one of the vertices in $S$. The two
predecessors other than $u$ of each vertex in $S$ must be a pair of
nonadjacent vertices in $N_{2}(v)\setminus\\{u\\}$ to avoid unique paths of
length 2 between vertices in $N_{2}(v)\setminus\\{u\\}$ and their non-neighbor
in $N_{3}(v)$. Additionally, the two successors of $a$ (respectively, $b$)
must have a common successor in $S$, otherwise there is a unique shortest path
of length 2 between $a$ (respectively, $b$) and a vertex in $S$. This implies
that the predecessors of a vertex in $S$ are $u$ and two nonadjacent vertices
in $N_{2}(v)$ that share a predecessor in $\\{a,b\\}$. Thus $G\cong K_{3}\Box
C_{4}$.

Case 3: $G[N_{1}(v)]$ contains exactly two edges, so $|S|=2$.

Then $q(G)>2$ by Lemma 5.1, Case 3 and the observation at the end of its
proof.

Case 4: $G[N_{1}(v)]$ contains exactly three edges, so $|S|=2$.

If $G[N_{1}(v)]\cong P_{4}$ or $G[N_{1}(v)]\cong C_{3}\cup K_{1}$, then by
Case 4 of Lemma 5.1 and the observations within its proof, there is a pair of
nonadjacent vertices with a unique path of length 2 between them. So we assume
$G[N_{1}(v)]\cong K_{1,3}$. As in that proof, $N_{2}(v)$ consists of three
vertices, each being the common successor of two leaves of the $K_{1,3}$.
Since $j=3$, there are two adjacent vertices of $S$ in $N_{3}(v)$, each with
three predecessors. Since $N_{2}(v)$ is an independent set, each of its three
vertices has two successors, so there are six edges between $N_{2}(v)$ and
$N_{3}(v)$. It can now be verified that $G\cong R_{10,3}$. For instance, let
$v$ correspond to vertex $1$ in the drawing of $R_{10,3}$ in Figure 4.

In all of the above cases, we either reach a contradiction to $q(G)=2$, or $G$
is isomorphic to either $R_{10,3}$ or $K_{3}\Box C_{4}$. Lemma 4.1 establishes
$q(R_{10,3})=2$. Since $K_{3}\Box C_{4}\cong K_{3}\Box K_{2}\Box K_{2}$,
Corollary 6.8 in [2] implies $q(K_{3}\Box C_{4})=2$. This completes the proof.
∎

######  Lemma 5.4.

If $G$ is a connected $4$-regular graph with $q(G)=2$ and diameter at least
$3$, then $G$ is either

  1. (1)

$K_{3}\Box C_{4}$, $K_{3,3}\Box K_{2}$, one of the graphs $R_{10,2}$,
$R_{10,3}$, $R_{10,4}$, $R_{12,3}$, or $R_{14,1}$ given in Figure 4;

  2. (2)

$Q_{4}$; or,

  3. (3)

a closed candle $H_{k}$ for some $k\geq 6$.

###### Proof.

Recall that a full vertex is a vertex whose incident edges have all been
accounted for.

Let $v$ be a vertex of $G$ with $\epsilon(v)\geq 3$. If no vertex in the
distance partition of $v$ has four predecessors, then $G\cong R_{10,3}$ or
$G\cong K_{3}\Box C_{4}$ by Lemma 5.3. For the remainder of this proof, we
assume that the distance partition of $v$ contains at least one vertex with
four predecessors. Let $d=\epsilon(v)$ be the index of the farthest distance
set. Each vertex with four predecessors uses two of the six extra edges, so
$N_{d}(v)$ may contain no more than three vertices with four predecessors.

Case 1: Exactly three vertices in $N_{d}(v)$, say $z_{1}$, $z_{2}$, and
$z_{3}$, have four predecessors.

All six of the extra edges are used by $z_{1}$, $z_{2}$, and $z_{3}$. By Case
1 of Lemma 5.1, $N_{2}(v)$ contains exactly six vertices, each being the
common successor of a different pair of vertices in $N_{1}(v)$, and $d=3$.
Since $N_{2}(v)$ has exactly six vertices with two successors each,
$N_{3}(v)=\\{z_{1},z_{2},z_{3}\\}$ and each vertex in $N_{2}(v)$ has two
neighbors in $\\{z_{1},z_{2},z_{3}\\}$.

Let $N_{2}(v)=\\{y_{1},y_{2},y_{3},y_{4},y_{5},y_{6}\\}$, and recall from Case
1 of Lemma 5.1 that each vertex in $N_{2}(v)$ shares a common predecessor in
$N_{1}(v)$ with exactly four other vertices in $N_{2}(v)$. This partitions
$N_{2}(v)$ into three pairs, say $\\{y_{1},y_{2}\\}$, $\\{y_{3},y_{4}\\}$, and
$\\{y_{5},y_{6}\\}$, where each pair does not share a predecessor in
$N_{1}(v)$. Since each $y_{i}$ has two successors among
$\\{z_{1},z_{2},z_{3}\\}$, each of these pairs must share at least one
successor in $N_{3}(v)$. Suppose $y_{1}$ and $y_{2}$ share $z_{1}$ as a common
successor. To avoid $y_{1}z_{1}y_{2}$ being a unique path of length 2, $y_{1}$
and $y_{2}$ must also share their second successor, say $z_{2}$. Similarly,
$\\{y_{3},y_{4}\\}$ and $\\{y_{5},y_{6}\\}$ each have two shared successors
among $\\{z_{1},z_{2},z_{3}\\}$. Without loss of generality, we may assume
that the successors of $\\{y_{3},y_{4}\\}$ are $\\{z_{1},z_{3}\\}$ and the
successors of $\\{y_{5},y_{6}\\}$ are $\\{z_{2},z_{3}\\}$. Thus $G\cong
R_{14,1}$, and Lemma 4.1 completes the proof.

Case 2: Exactly two vertices in $N_{d}(v)$, say $z_{1}$ and $z_{2}$, have four
predecessors.

In this case there remain two extra edges. We treat the possibilities for
these edges in the following four subcases.

Case 2(a): $z_{1}$ and $z_{2}$ share all their predecessors in $N_{d-1}(v)$.

Denote the common predecessors of $z_{1}$ and $z_{2}$ by
$\\{y_{1},y_{2},y_{3},y_{4}\\}$. Suppose $d>3$. Let
$\\{x_{1},x_{2}\\}\subseteq N_{d-2}(v)$ denote the predecessors of $y_{1}$. If
$x_{1}$ has three predecessors, then $y_{1}$ is its unique successor, and
$x_{1}y_{1}z_{1}$ is a unique shortest path of length 2 between $x_{1}$ and
$z_{1}$. So we may let $\\{w_{1},w_{2}\\}\subseteq N_{d-3}(v)$ denote the
predecessors of $x_{1}$. Since $y_{1}$ is full and $w_{1}x_{1}y_{1}$ is a
shortest path of length 2, $w_{1}$ must be adjacent to $x_{2}$. Similarly,
$w_{2}$ is adjacent to $x_{2}$. We repeat this argument, with $x_{1}$
replacing $y_{1}$, and then with $w_{1}$ replacing $x_{1}$, forming successive
induced candle sections from $\\{x_{1},x_{2}\\}$ until we reach, say,
$\\{a_{1},a_{2}\\}\subseteq N_{1}(v)$. Since both $x_{1}$ and $x_{2}$ are just
one edge short of being full, there must exist a vertex, say $y_{4}$, whose
predecessors are not $x_{1}$ or $x_{2}$. Denote the predecessors of $y_{4}$ by
$\\{x_{3},x_{4}\\}$. By the same argument, starting with $y_{4}$ we see
successive induced candle sections from $\\{x_{3},x_{4}\\}$ until
$\\{a_{3},a_{4}\\}\subseteq N_{1}(v)$. Recall that
$\\{x_{1},x_{2}\\}\cap\\{x_{3},x_{4}\\}=\emptyset$. A vertex in
$\\{w_{1},w_{2}\\}\cap\\{w_{3},w_{4}\\}$ would have to have four successors,
so $\\{w_{1},w_{2}\\}\cap\\{w_{3},w_{4}\\}=\emptyset$. Continuing, the two
candle sections must be disjoint, including
$\\{a_{1},a_{2}\\}\cap\\{a_{3},a_{4}\\}=\emptyset$. It follows that
$N_{1}(v)=\\{a_{1},a_{2},a_{3},a_{4}\\}$.

Suppose the two predecessors of $y_{2}$ are $x_{i}\in\\{x_{1},x_{2}\\}$ and
$x_{j}\in\\{x_{3},x_{4}\\}$. Then $x_{i},x_{j}$, and $y_{2}$ are all full, and
$x_{i}y_{2}x_{j}$ is a unique shortest path of length 2 between $x_{i}$ and
$x_{j}$. So we assume without loss of generality that the predecessors of
$y_{2}$ are $\\{x_{1},x_{2}\\}$, and of $y_{3}$ are $\\{x_{3},x_{4}\\}$.

Each vertex in $N_{1}(v)$ is one edge short of being full, and any pair of
these vertices shares $v$ as a common neighbor. Suppose $a_{1}$ is adjacent to
one of $\\{a_{3},a_{4}\\}$, say $a_{3}$. Then $a_{1}$ and $a_{3}$ are both
full, and $a_{1}va_{4}$ is a unique shortest path of length 2 between $a_{1}$
and $a_{4}$. So $a_{1}$, $a_{3}$, and $a_{4}$ must share a common successor
$u\in N_{2}(v)$. Similarly, $a_{2}$, $a_{3}$, and $a_{4}$ must share a common
successor, which must be $u$ since $a_{3}$ and $a_{4}$ are full. Therefore,
$u$ has four predecessors, using up the remaining two extra edges, and all
vertices listed so far are full. It follows that $G$ cannot contain any
additional vertices, and $G\cong H_{k}$ for some even $k\geq 6$ (as the number
of vertices accounted for in the proof is divisible by $4$). Recall that
$q(H_{k})=2$ by Lemma 2.3.

Suppose $d=3$ and again write $N_{1}(v)=\\{a_{1},a_{2},a_{3},a_{4}\\}$. The
exact number of edges that connect $\\{y_{1},y_{2},y_{3},y_{4}\\}$ to vertices
in $N_{1}(v)$ is eight. Furthermore, since $z_{1}$ and $z_{2}$ are full, each
vertex in $N_{1}(v)$ must have either zero or at least two successors in
$\\{y_{1},y_{2},y_{3},y_{4}\\}$, to prevent a unique shortest path of length 2
between $N_{1}(v)$ and $N_{3}(v)$. If, say $a_{1}$, has no successor in
$\\{y_{1},y_{2},y_{3},y_{4}\\}$, then it must be adjacent to each of
$\\{a_{2},a_{3},a_{4}\\}$. However, to account for the edges between
$N_{1}(v)$ and $N_{2}(v)$, some $a_{i}$ must have three successors. This is
impossible as $\deg(a_{i})=4$ for all $i$. So each $a_{i}$ has two successors
in $\\{y_{1},y_{2},y_{3},y_{4}\\}$, accounting for eight edges. These eight
edges and $\\{y_{1},y_{2},y_{3},y_{4}\\}\cup\\{a_{1},a_{2},a_{3},a_{4}\\}$
form $2C_{4}$ or $C_{8}$. In the first case, it follows as in the previous
paragraph that $G\cong H_{6}$.

Suppose the eight edges connecting the vertices
$\\{y_{1},y_{2},y_{3},y_{4}\\}$ to $\\{a_{1},a_{2},a_{3},a_{4}\\}$ form a
$C_{8}$. Then there are two pairs of vertices in $N_{1}(v)$ that share $v$ as
a predecessor but share no successor in $\\{y_{1},y_{2},y_{3},y_{4}\\}$.
Without loss of generality, assume these pairs are $\\{a_{1},a_{3}\\}$ and
$\\{a_{2},a_{4}\\}$. Suppose the two remaining extra edges are contained in
$N_{1}(v)$. Then the two non-isomorphic ways to place these edges are
$\\{a_{1}a_{2},a_{3}a_{4}\\}$ or $\\{a_{1}a_{3},a_{2}a_{4}\\}$. In the first
case, $a_{1}va_{3}$ is a unique shortest path of length 2. If $a_{1}a_{3}$ and
$a_{2}a_{4}$ are edges, and if the common successor of $a_{1}$ and $a_{4}$ is,
say $y_{1}$, then $y_{1}a_{1}a_{3}$ is a unique shortest path of length 2
between $y_{1}$ and $a_{3}$. Therefore $N_{1}(v)$ cannot contain two edges and
there is at least one (and at most two) additional vertex (vertices) in
$N_{2}(v)$.

In either case, a vertex $y_{5}\notin\\{y_{1},y_{2},y_{3},y_{4}\\}$ cannot
have a successor, since there would be a unique shortest path of length 2
between this successor and the predecessors of $y_{5}$ in $N_{1}(v)$. So
$y_{5}$ must be a terminal vertex. Because we have only two extra edges
remaining, $y_{5}$ must have at most one neighbor in $N_{2}(v)$ and hence must
have at least three predecessors. If there were a second terminal vertex
$y_{6}\in N_{2}(v)$, then there would be at least six edges from
$\\{y_{5},y_{6}\\}$ to $N_{1}(v)$, contradicting that all four vertices in
$N_{1}(v)$ are only one edge short of being full. The only possibility then is
for $N_{2}(v)$ to contain the one additional vertex, $y_{5}$, with all four
vertices in $N_{1}(v)$ as its predecessors, using up the two remaining extra
edges. Then all vertices are full, and in this case $G\cong R_{12,1}$, which
satisfies $q(R_{12,1})>2$, by Lemma 4.1, and leads to a contradiction.

Case 2(b): $z_{1}$ and $z_{2}$ share exactly three of their four predecessors
in $N_{d-1}(v)$.

Denote the predecessors of $z_{1}$ by $\\{y_{1},y_{2},y_{3},y_{4}\\}$ and of
$z_{2}$ by $\\{y_{2},y_{3},y_{4},y_{5}\\}$. Then $y_{1}$ shares one common
successor with $y_{2}$, $y_{3}$, and $y_{4}$. Given that these three vertices
have two predecessors each, they are full, as is their other successor
$z_{2}$. So $y_{1}$ cannot be adjacent to any of them, nor can it have a
second common successor with any of them. Therefore, $y_{1}$ must have a
common predecessor with each of $y_{2}$, $y_{3}$, and $y_{4}$. In particular,
let $x_{1}$ be a common predecessor of $y_{1}$ and $y_{2}$. Then the path
$x_{1}y_{2}z_{2}$ implies $x_{1}$ must be adjacent to $y_{3}$, $y_{4}$, or
$y_{5}$, which implies $x_{1}\in N_{1}(v)$ and $d=3$. Denote the three
remaining vertices in $N_{1}(v)$ by $\\{x_{2},x_{3},x_{4}\\}$. Moreover, the
fullness of $z_{1}$, $y_{2}$, $y_{3}$, and $y_{4}$ implies that any neighbor
of $y_{1}$ other than $z_{1}$ must be its predecessor (to avoid a unique
shortest path of length 2 between $z_{1}$ and this neighbor of $y_{1}$), and
hence $y_{1}$ has three predecessors in $N_{1}(v)$. Similarly, $y_{5}$ has
three predecessors in $N_{1}(v)$, using up the two remaining extra edges.

We make two observations. First, since there are exactly twelve edges
connecting $\\{y_{1},y_{2},y_{3},y_{4},y_{5}\\}$ to vertices in $N_{1}(v)$,
any successor of $x_{1}$, $x_{2}$, $x_{3}$, and $x_{4}$ must be in
$\\{y_{1},y_{2},y_{3},y_{4},y_{5}\\}$, and

$V(G)=\\{z_{1},z_{2},y_{1},y_{2},y_{3},y_{4},y_{5},x_{1},x_{2},x_{3},x_{4},v\\}.$

Second, $y_{1}$ and $y_{5}$ share at least two predecessors.

Suppose $y_{1}$ and $y_{5}$ share all three predecessors, say
$\\{x_{1},x_{2},x_{3}\\}$. Then the three successors of $x_{4}$ must be
$y_{2}$, $y_{3}$, and $y_{4}$. Finally, the remaining predecessor of $y_{3}$
and $y_{4}$ must be, without loss of generality, $x_{2}$ and $x_{3}$,
respectively. Hence all vertices are full, and $G\cong K_{3,3}\Box K_{2}$.
Corollaries 6.5 and 6.8 of [2] show that $q(K_{3,3}\Box K_{2})=2$.

Now suppose $y_{1}$ and $y_{5}$ share two predecessors, say
$\\{x_{1},x_{2}\\}$. Without loss of generality, let $x_{3}$ and $x_{4}$ be
the third predecessors of $y_{1}$ and $y_{5}$, respectively. Either $x_{1}$
and $x_{2}$ share their third successor as well or they do not. Suppose
$x_{1}$ and $x_{2}$ share all three successors, $\\{y_{1},y_{2},y_{5}\\}$.
Then $y_{1}$, $y_{2}$, and $y_{5}$ are all full, and the four remaining edges
between $N_{2}(v)$ and $N_{1}(v)$ are determined. In this case, $G\cong
R_{12,2}$, contradicting $q(G)=2$ by Lemma 4.1. Therefore, we must have that
$x_{1}$ and $x_{2}$ do not share a third common successor. Since the third
successor of $x_{1}$ is $y_{2}$, let the third successor of $x_{2}$ be
$y_{3}$. Again, the four remaining edges between $N_{2}(v)$ and $N_{1}(v)$ are
determined, up to one choice, which yields graphs that are isomorphic. In this
case, it can be verified that $G\cong R_{12,3}\cong C(12,\pm 1,\pm 3)$, and
Lemma 4.1 implies $q(R_{12,3})=2$.

Case 2(c): $z_{1}$ and $z_{2}$ share exactly two of their four predecessors in
$N_{d-1}(v)$.

Suppose the predecessors of $z_{1}$ are $\\{y_{1},y_{2},y_{3},y_{4}\\}$ and
the predecessors of $z_{2}$ are $\\{y_{3},y_{4},y_{5},y_{6}\\}$. With two
predecessors, $y_{3}$ is full (as is $y_{4}$). To resolve the unique shortest
paths of length 2 through $z_{1}$ or $z_{2}$, $y_{3}$ must share a predecessor
with each of $y_{1},y_{2},y_{5}$, and $y_{6}$. It follows that the
predecessors of $y_{3}$ have three successors each, and therefore $d=3$.

Since there are at least twelve edges from
$\\{y_{1},y_{2},y_{3},y_{4},y_{5},y_{6}\\}$ to $N_{1}(v)$, and at most twelve
edges from $N_{1}(v)$ to $N_{2}(v)$, we must have:
$N_{2}(v)=\\{y_{1},y_{2},y_{3},y_{4},y_{5},y_{6}\\}$, each vertex in
$N_{2}(v)$ has exactly two predecessors in $N_{1}(v)$, and each vertex in
$N_{1}(v)$ has exactly three successors in $N_{2}(v)$. Note that $y_{3}$ and
$y_{4}$ are full while $y_{1}$, $y_{2}$, $y_{5}$, and $y_{6}$ are each one
edge short of full. We label $N_{1}(v)=\\{x_{1},x_{2},x_{3},x_{4}\\}$.

To prevent unique shortest paths of length 2 between $x_{i}$ and $z_{j}$, each
$x_{i}$ must be adjacent to at least one vertex in $\\{y_{3},y_{4}\\}$. It
follows that each $x_{i}$ must have exactly one neighbor in
$\\{y_{3},y_{4}\\}$. Assume one successor of $x_{1}$ is $y_{3}$. To avoid
unique paths of length 2 between $x_{1}$ and both $z_{1}$ and $z_{2}$, $x_{1}$
must have at least one more successor in $\\{y_{1},y_{2}\\}$ and at least one
more successor in $\\{y_{5},y_{6}\\}$. Assume, without loss of generality,
that the successors of $x_{1}$ are $\\{y_{1},y_{3},y_{5}\\}$. Suppose $y_{1}$
has a successor, $z_{3}$, in addition to $z_{1}$. Then $z_{3}$ must be
adjacent to $y_{5}$ (to prevent $x_{1}y_{1}z_{3}$ being a unique shortest path
of length 2 between $x_{1}$ and $z_{3}$) and $z_{3}$ must be adjacent to
$y_{6}$ (to prevent $z_{3}y_{5}z_{2}$ being a unique shortest path of length 2
between $z_{3}$ and $z_{2}$). This leaves all vertices in $N_{2}(v)$ except
$y_{2}$ full, but any successor of $y_{2}$ distinct from $z_{1}$, $z_{2}$, and
$z_{3}$ would create a unique shortest path of length 2 between this successor
and a predecessor of $y_{2}$. So the successor of $y_{2}$ must be $z_{3}$,
contradicting the assumption of Case 2.

To become full, $y_{1}$ must have exactly one neighbor in
$\\{y_{2},y_{5},y_{6}\\}$. If $y_{1}$ is adjacent to $y_{2}$, then
$x_{1}y_{1}y_{2}$ is a unique shortest path of length 2 between the full
vertices $x_{1}$ and $y_{2}$. But if $y_{1}$ is adjacent to $y_{5}$ or
$y_{6}$, then $z_{1}y_{1}y_{5}$ or $z_{1}y_{1}y_{6}$ is a unique shortest path
of length 2 between $z_{1}$ and $y_{5}$ or $y_{6}$, respectively, which would
contradict $q(G)=2$.

Case 2(d): $z_{1}$ and $z_{2}$ share exactly one, or none, of their four
predecessors in $N_{d-1}(v)$.

Here $N_{d-1}(v)$ must contain seven or eight vertices, at least six of which,
after accounting for two predecessors, are exactly one edge short of being
full. If any such $y\in N_{d-1}(v)$ has another successor $z_{3}\in N_{d}(v)$,
then $z_{3}$ must have a neighbor $z_{4}\in
N_{d}(v)\setminus\\{z_{1},z_{2}\\}$. Since $y$, $z_{1}$, and $z_{2}$ are full,
$yz_{3}z_{4}$ is a unique shortest path of length 2 between $y$ and $z_{4}$.
In order for the vertices in $N_{d-1}(v)$ to become full, at least six
vertices require incidence with one of the two remaining extra edges, which is
impossible.

Case 3: Exactly one vertex, say $z$, in $N_{d}(v)$ has four predecessors.

Four extra edges remain. Denote the predecessors of $z$ by
$\\{y_{1},y_{2},y_{3},y_{4}\\}\subseteq N_{d-1}(v)$.

Case 3(a): $y_{1}$, $y_{2}$, $y_{3}$, and $y_{4}$ each have three
predecessors.

All remaining extra edges are used, and $N_{d}(v)=\\{z\\}$ and
$N_{d-1}(v)=\\{y_{1},y_{2},y_{3},y_{4}\\}$. Suppose $d=3$. Each vertex in
$N_{1}(v)$ has three successors in $N_{2}(v)$ (to account for the twelve edges
connecting $N_{2}(v)$ to $N_{1}(v)$), and each $y_{i}$ has one vertex in
$N_{1}(v)$ as its non-neighbor. If $y_{i}\neq y_{j}$ have the same non-
neighbor, then that vertex cannot have three successors. So the four vertices
in $N_{2}(v)$ are in bijection with the four vertices in $N_{1}(v)$, via non-
neighbors, determining the graph as $G\cong R_{10,4}$. Lemma 4.1 shows
$q(R_{10,4})=2$.

Suppose $d>3$. Each pair of vertices in $\\{y_{1},y_{2},y_{3},y_{4}\\}$ shares
$z$ as a common successor, and each $y_{i}$ is full with three predecessors,
so each pair must share a common predecessor in $N_{d-2}(v)$. The vertices in
$N_{d-2}(v)$ must have two predecessors each and therefore can have at most
two successors in $N_{d-1}(v)$. This forces $N_{d-2}(v)$ to contain six
vertices $\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$, each being the common
predecessor of a different pair of vertices in
$\\{y_{1},y_{2},y_{3},y_{4}\\}$, exhausting all edges between
$\\{y_{1},y_{2},y_{3},y_{4}\\}$ and
$\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$.

Consider $y_{1}$ and, without loss of generality, let
$\\{x_{1},x_{2},x_{3}\\}$ denote its three predecessors. Then $x_{4}$,
$x_{5}$, and $x_{6}$ each must have their two successors in
$\\{y_{2},y_{3},y_{4}\\}$. We claim that $x_{4}$, $x_{5}$, and $x_{6}$ must
have a common predecessor in $N_{d-3}(v)$. Note that if $x_{4}$, $x_{5}$ and
$x_{6}$ have a common predecessor, this predecessor must lie in $N_{1}(v)$,
and $d=4$. Indeed, if any two of $\\{x_{4},x_{5},x_{6}\\}$ share a
predecessor, then all three must share a predecessor, in order to prevent a
unique shortest path of length 2 between this predecessor and one of
$\\{y_{2},y_{3},y_{4}\\}$. However, if $x_{4}$, $x_{5}$, and $x_{6}$ have
three distinct predecessors in $N_{d-3}(v)$ that are not predecessors of
either of the other two, then each of these three predecessors must have two
successors in $\\{x_{1},x_{2},x_{3}\\}$, thereby causing $x_{1}$, $x_{2}$, and
$x_{3}$ to be full; the fourth vertex of $N_{d-3}(v)=N_{1}(v)$ must then have
$x_{4}$, $x_{5}$, and $x_{6}$ as its three successors.

Let $w_{1}$ be a shared predecessor of $\\{x_{4},x_{5},x_{6}\\}$. Then there
are two paths of length 2 between $w_{1}$ and each of
$\\{y_{2},y_{3},y_{4}\\}$ and no paths of length 2 between $w_{1}$ and
$y_{1}$. Repeat this procedure for $y_{2}$, $y_{3},$ and $y_{4}$, each time
finding a common predecessor $w_{i}$ of

$\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}\setminus\\{\mbox{predecessors of
}y_{i}\\}$

for $i=2,3,4$. The choice of edges between $\\{y_{1},y_{2},y_{3},y_{4}\\}$ and
$\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$ therefore determines the edges
between $\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$ and
$\\{w_{1},w_{2},w_{3},w_{4}\\}$. However, since all pairs of vertices in
$\\{y_{1},y_{2},y_{3},y_{4}\\}$ share a predecessor among the independent set
$\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$ of vertices, all choices yield
isomorphic graphs. All vertices are now full, so we have listed all elements
of each distance set, and $G\cong Q_{4}$. By [2] Corollary 6.9, $q(Q_{4})=2$.

Case 3(b): There exists a vertex in $N_{d-1}(v)$, say $y_{1}$, that does not
have three predecessors.

The edges incident with $z$ account for two of the extra edges. If $y_{1}$ has
another successor $z_{2}\in N_{d}(v)$, then $z_{2}$ must have a neighbor
$z_{3}\in N_{d}(v)\setminus\\{z,z_{2}\\}$; since $y_{1}$ (with two
predecessors) and $z$ are both full, $y_{1}z_{2}z_{3}$ is a unique shortest
path of length 2 between $y_{1}$ and $z_{3}$. So $y_{1}$ must have a neighbor
$u\in N_{d-1}(v)$, using up an extra edge.

Suppose $u\notin\\{y_{2},y_{3},y_{4}\\}$. Then $u$ must be adjacent to another
vertex in $\\{y_{1},y_{2},y_{3},y_{4}\\}$, say $y_{2}$, to avoid a unique
shortest path of length 2 between itself and $z$. This leaves two remaining
extra edges. Let $x_{1}$ and $x_{2}$ denote the two predecessors of $u$.
Suppose $x_{1}$ has two predecessors. Then it cannot be adjacent to both
$y_{1}$ and $y_{2}$. So there must exist $x_{3}\in N_{d-2}(v)$ (possibly
$x_{3}=x_{2}$) such that $x_{1}$ is adjacent to $x_{3}$, and $x_{3}$ is
adjacent to $y_{1}$ and $y_{2}$. But then $x_{3}$ can have only one
predecessor, so we must have $d=3$.

Let $N_{1}(v)=\\{x_{1},x_{2},x_{3},x_{4}\\}$. If $x_{1}$ and $x_{2}$ are not
incident with an edge of $G[N_{1}(v)]$, then $x_{1}$ and $x_{2}$ both must be
adjacent to $\\{u,y_{1},y_{2}\\}$ (to avoid uniqueness of the shortest paths
between each $x_{1}$, $x_{2}$ and each $y_{1}$, $y_{2}$ through $u$); but then
$y_{1}$ and $y_{2}$ are full, and $y_{1}zy_{3}$ is a unique shortest path of
length 2 between $y_{1}$ and $y_{3}$. Hence $G[N_{1}(v)]$ must contain an
edge, using a third extra edge. It follows that there are exactly ten edges
connecting $N_{1}(v)$ to $N_{2}(v)$. Then no vertex in $N_{2}(v)$ can have
three predecessors, which implies $G[N_{2}(v)]$ must contain another edge, the
last of the extra edges. Moreover, this edge must connect $y_{3}$ and $y_{4}$.
Note this implies $N_{1}(v)$ cannot be an independent set of vertices.

Suppose $x_{2}$ is incident with the edge in $G[N_{1}(v)]$, and $x_{1}$ is
not. Then $x_{1}$ must be adjacent to $\\{u,y_{1},y_{2}\\}$. And since $x_{1}$
shares $v$ as a common predecessor with $x_{3}$ and $x_{4}$, and since $u$ is
full while $y_{1}$ and $y_{2}$ are one edge short of being full, we must have,
without loss of generality, $y_{1}$ adjacent to $x_{3}$ and $y_{2}$ adjacent
to $x_{4}$. Since $x_{1}$ and $y_{1}$ are full, the uniqueness of the path
$x_{2}uy_{1}$ can only be avoided if $x_{2}$ is adjacent to $x_{3}$.
Similarly, the uniqueness of the path $x_{2}uy_{2}$ can only be avoided if
$x_{2}$ is adjacent to $x_{4}$. But $G[N_{1}(v)]$ can only have one edge.

So the edge in $G[N_{1}(v)]$ must be $x_{1}x_{2}$. Then $x_{1}$ has only one
more successor in $N_{2}(v)$ which must simultaneously resolve $v$ being the
unique common neighbor of the pairs $\\{x_{1},x_{3}\\}$ and
$\\{x_{1},x_{4}\\}$. This successor must then have three predecessors, which
is impossible. Therefore $u\in\\{y_{2},y_{3},y_{4}\\}$.

Without loss of generality, suppose $u=y_{2}$. As at the start of this case,
$\\{y_{1},y_{2},y_{3},y_{4}\\}$ can have no more successors in $N_{d}(v)$. And
$y_{1}$ and $y_{2}$ cannot be incident to another edge in $G[N_{d-1}(v)]$, in
order to allow for each to have two predecessors. To prevent $y_{1}$ and
$y_{3}$ having $z$ as a unique common neighbor, they must therefore share a
common predecessor, say $x_{1}\in N_{d-2}(v)$. If $x_{1}$ has two
predecessors, then it is full, and $x_{1}y_{1}y_{2}$ is a unique shortest path
of length 2 between $x_{1}$ and $y_{2}$. So $x_{1}$ must have only one
predecessor, which implies $d=3$.

Suppose that $G[N_{2}(v)]$ contains no edges other than $y_{1}y_{2}$; then
$y_{3}$ and $y_{4}$ must have three predecessors each. Denote the other
vertices in $N_{1}(v)$ by $x_{2}$, $x_{3}$, and $x_{4}$. Now, $y_{3}$ and
$y_{4}$ must share at least two of their predecessors in $N_{1}(v)$, but
$x_{1}$ cannot be this shared predecessor, since that would leave
$x_{1}y_{1}y_{2}$ as the unique shortest path of length 2 between $x_{1}$ and
$y_{2}$. So assume the two shared predecessors of $y_{3}$ and $y_{4}$ are
$\\{x_{3},x_{4}\\}$. Neither $x_{3}$ nor $x_{4}$ can be adjacent to $y_{1}$ or
$y_{2}$, as these adjacencies would result in a unique shortest path of length
2 between one of $\\{x_{3},x_{4}\\}$ and one of $\\{y_{1},y_{2}\\}$. With
exactly one remaining extra edge, this edge must be $x_{3}x_{4}$ to ensure
that $x_{3}$ and $x_{4}$ each have four neighbors. It now follows that $x_{1}$
is adjacent to $y_{2}$, and hence the three remaining edges are $x_{2}y_{1}$,
$x_{2}y_{2}$, and $x_{2}y_{4}$. After connecting each $x_{i}$ to $v$, all
vertices are full, and $G\cong R_{10,3}$ (to see this let $v$ be vertex $3$ in
the drawing of $R_{10,3}$ in Figure 4). Applying Lemma 4.1 establishes
$q(R_{10,3})=2$.

Finally, suppose $G[N_{2}(v)]$ contains another edge, which can only be
$y_{3}y_{4}$, as otherwise $y_{1}$ or $y_{2}$ would not have enough
predecessors. So each $y_{i}$ has exactly two predecessors. Then there are
eight edges between $N_{2}(v)$ and $N_{1}(v)$, and each vertex in $N_{1}(v)$
must have exactly two successors. Each pair $\\{y_{1},y_{3}\\}$,
$\\{y_{1},y_{4}\\}$, $\\{y_{2},y_{3}\\}$, and $\\{y_{2},y_{4}\\}$ must share a
single predecessor in $N_{1}(v)$, causing each $y_{i}$ to be full. Denote
these unique common predecessors by $x_{1}$, $x_{2}$, $x_{3}$, and $x_{4}$,
respectively. To simultaneously avoid the unique shortest paths of length 2
from $x_{1}$ to $y_{2}$ and $y_{4}$, $x_{1}$ must be adjacent to $x_{4}$.
Similarly, $x_{2}$ must be adjacent to $x_{3}$. This uses up the remaining
extra edges. After connecting each $x_{i}$ to $v$, all vertices are full, and
$G\cong R_{10,2}$. Using Lemma 4.1 establishes $q(R_{10,2})=2$.

Case 4: $N_{d}(v)$ contains no vertices with four predecessors.

Since the distance partition from $v$ contains at least one vertex with four
predecessors, let $b$ denote a vertex with four predecessors. This accounts
for two of the six extra edges. By the proofs of Lemmas 5.1 and 5.3,
$N_{d}(v)$ must contain a pair of vertices with three predecessors each or a
cycle of vertices with two predecessors each. Furthermore, each edge in
$N_{d}(v)$ is an extra edge and any vertex in $N_{d}(v)$ with three
predecessors accounts for an extra edge, and so $G[N_{d}(v)]$ must be
isomorphic to one of $K_{2}$, $P_{3}$, $C_{3}$, or $C_{4}$. Each of these
options requires either three or four of the remaining extra edges. Therefore,
there is at most one extra edge unaccounted for. This implies $b$ is the
unique vertex with four predecessors.

We first claim that $b\in N_{2}(v)$. Indeed, suppose $b\in N_{i}(v)$ for some
$2<i<d$, and let $\\{a_{1},a_{2},a_{3},a_{4}\\}\subseteq N_{i-1}(v)$ be the
four predecessors of $b$. Then each $a_{i}$ has at least two predecessors.
With at most one of the extra edges left, we may assume, without loss of
generality, that $a_{1}$ has a successor $b_{1}\in N_{i}(v)$. Now, $b_{1}$
cannot be a terminal vertex, as that would require more extra edges than are
currently unaccounted for, so let $c_{1}\in N_{i+1}(v)$ be a successor of
$b_{1}$. Then $a_{1}b_{1}c_{1}$ is a unique shortest path of length 2. So
$b\in N_{2}(v)$.

We next claim that there are no vertices with three predecessors in $N_{i}(v)$
for any $i<d$. As observed at the end of Claim #1 in the proof of Lemma 5.3,
any successor of a vertex with three predecessors must be a vertex with four
predecessors. Since $b\in N_{2}(v)$, any vertex with three predecessors in
$N_{i}(v)$ for $i\geq 2$ cannot have a successor. It follows that such a
vertex requires an edge in $G[N_{i}(v)]$, which would require the use of at
least three extra edges. A similar argument shows that any vertex in
$N_{i}(v)$ for $2\leq i<d-1$ cannot have a unique successor in $N_{i+1}(v)$.
If there were a vertex $x$ with two predecessors and a unique successor $y$,
it must be adjacent to another vertex in $N_{i}(v)$. Then $y$ must either be
adjacent to a vertex in $N_{i+2}(v)$ or $N_{i+1}(v)$ yielding either a unique
shortest path or too many extra edges. So, with the exception of $b$, every
vertex in $N_{i}(v)$ for $2\leq i<d$ has exactly two predecessors, and every
vertex in $N_{i}(v)$ for $2\leq i<d-1$ has exactly two successors.

We have $\\{a_{1},a_{2},a_{3},a_{4}\\}=N_{1}(v)$, and $b$ is a common
successor of these four vertices. With only one remaining extra edge, each
$a_{i}$ must have another successor in $N_{2}(v)$. Let $b_{1}\neq b$ be a
successor of $a_{1}$ in $N_{2}(v)$, let $a_{2}$ be the second predecessor of
$b_{1}$, and let $c_{1}\in N_{3}(v)$ be a successor of $b_{1}$. Note that this
implies $a_{1}$ and $a_{2}$ are not adjacent. To avoid unique paths of length
2 between $c_{1}$ and each of $a_{1}$ and $a_{2}$, the second predecessor of
$c_{1}$, say $b_{2}$, must have $a_{1}$ and $a_{2}$ as its predecessors.
Continuing in this way through $N_{i}(v)$ for all $3\leq i\leq d-2$, we see
successive induced candle sections starting with $\\{a_{1},a_{2}\\}$, and
ending say at $\\{y_{1},y_{2}\\}\subseteq N_{d-1}(v)$. Let $z_{1}$ be the
common successor of $\\{y_{1},y_{2}\\}$ in $N_{d}(v)$. This argument is
similar to the argument we used in Case 2(a). Starting again from $a_{3}$, we
see successive induced candle sections starting with $\\{a_{3},a_{4}\\}$ and
ending at say $\\{y_{3},y_{4}\\}\subseteq N_{d-1}(v)$ whose common successor
is $z_{2}\in N_{d}(v)$.

Note that all vertices in $N_{i}(v)$ for $i<d-1$ are full, which implies
$N_{d-1}(v)=\\{y_{1},y_{2},y_{3},y_{4}\\}$. Each $N_{i}(v)$ is independent for
$i<d-1$, and we claim that $N_{d-1}(v)$ is independent as well. To see this,
$y_{i}y_{j}$ an edge for $i\in\\{1,2\\}$ and $j\in\\{3,4\\}$ would create a
unique shortest path of length 2 from $N_{d-1}(v)$ to $N_{d-2}(v)$. If
$y_{1}y_{2}$ is an edge, then $y_{1}$ and $y_{2}$ are full and hence
$y_{1}z_{1}z$ is a unique shortest path for any neighbor $z$ of $z_{1}$ in
$N_{d}(v)$. The same observation shows $y_{3}y_{4}$ cannot be an edge. Hence
the last remaining extra edge must be in $G[N_{d}(v)]$. This implies that
$G[N_{d}(v)]$ is either isomorphic to $P_{3}$ or $C_{4}$. Note that if some
vertex in $N_{d}(v)$ has three predecessors, then without loss of generality,
it is adjacent to $y_{1}$, $y_{2}$, and $y_{3}$. This results in a unique
shortest path of length 2 through $y_{3}$. Thus $G[N_{d}(v)]\cong C_{4}$.

We now claim that any successor of $y_{1}$ or $y_{2}$ must be a successor of
both. Indeed, if $z$ is a successor of $y_{1}$, then the paths $zy_{1}x_{1}$
and $zy_{1}x_{2}$ force $z$ to be adjacent to $y_{2}$ as well. Similarly, any
successor of $y_{3}$ or $y_{4}$ must be a successor of both. Hence we have
four vertices in $N_{d}(v)$ forming a cycle $C_{4}$ where each vertex is
adjacent to either $\\{y_{1},y_{2}\\}$ or $\\{y_{3},y_{4}\\}$. This implies
that the vertices around the cycle must alternate between being adjacent to
$\\{y_{1},y_{2}\\}$ and $\\{y_{3},y_{4}\\}$ and so $G\cong H_{k}$ for some odd
$k\geq 7$ (as the size of $V(G)\setminus\\{b,v\\}$ is divisible by 4).
Applying Lemma 2.3 establishes $q(H_{k})=2$.

∎

This completes the proof of Theorem 2.4.

##  6 Further Observations and Related Problems

Corollary 2.2 and Theorem 2.4 give a complete characterization of the
$r$-regular graphs that admit two distinct eigenvalues for $r\leq 4$. For
$r=4$, the closed candles $H_{k}$ for $k\geq 3$ give the only infinite family
of $4$-regular graphs $G$ with $q(G)=2$. From these graphs we can construct an
infinite family of $r$-regular graphs $G$ with $q(G)=2$ for all $r\geq 5$.

From Corollary 6.8 in [2], if $G$ is any graph with $q(G)=2$, then $q(G\Box
K_{2})=2$. Define $H_{k}^{d}=H_{k}\Box Q_{d}$ for any $d\geq 0$ and $k\geq 3$.
Now from Lemma 2.3 and [2, Cor. 6.9] we immediately have the following result.

######  Proposition 6.1.

For all $k\geq 3$ and $d\geq 0$, $H_{k}^{d}$ is a $(4+d)$-regular graph with
$q(H_{k}^{d})=2$.

When $r\geq 5$, the number of edges in an $r$-regular graph grows faster than
the lower bound $|E(G)|\geq 2n-4$. So, characterizing $r$-regular graphs with
two distinct eigenvalues for $r\geq 5$ could be difficult using the methods in
this paper. This motivates questions about existence and structure of such
graphs. That is, are there other infinite families of $r$-regular graphs $G$
with $q(G)=2$, and if so, can they be constructed with a method other than the
Cartesian product used in Proposition 6.1?

######  Problem 6.2.

Determine whether or not an infinite family of $5$-regular graphs $G$ with
$q(G)=2$ disjoint from the family $\\{H_{k}^{1}\,:\,k\geq 3\\}$ exists.

This paper builds on the work in [6], where we established a lower bound on
the number of edges a graph on $n$ vertices must have in order to have
$q(G)=2$, and characterized the graphs that meet the bound with equality. The
graphs that meet the bound $|E(G)|\geq 2n-4$ are $Q_{3}$ and an infinite
family of graphs called _double-ended candles_. The lower bound is improved to
$|E(G)|\geq 2n-3$ if $G$ has an odd number of vertices, and the graphs that
meet this improved bound are exactly the infinite family of graphs called
_single-ended candles_. These graphs, along with the closed candles $H_{k}$
and some of the sporadic graphs in Theorem 2.4, appear in a set of papers
focusing on a different problem.

McKee and Smyth [19], Taylor [21], and Greaves [12, 13] all consider the
following problem: for which graphs $G$ is there a matrix _compatible_ with
$G$ whose eigenvalues are contained in the interval $[-2,2]$? For this
problem, “compatible” means that the matrix $M$ has exactly the same zero
pattern as $A(G)$ off of the diagonal entries, and the entries of $M$ are
restricted to lie in the ring of integers for some quadratic field (McKee and
Smyth consider matrices with integer entries. Taylor and Greaves consider
matrices whose entries lie in the ring of integers for an imaginary quadratic
extension of $\mathbb{Q}$). It follows from interlacing that if $G$ has a
compatible matrix whose eigenvalues are contained in $[-2,2]$, then so do all
of its induced subgraphs. This motivates the characterization of the maximal
graphs $G$ for which there is a matrix compatible with $G$ whose eigenvalues
are contained in $[-2,2]$. Each of the papers [19], [12], [13], and [21] gives
a characterization for the respective rings under consideration. The graphs
that appear in these characterizations are a collection of small sporadic
graphs, and a few infinite families: the single-ended candles, the double-
ended candles, the closed candles, and the graphs obtained from a candle
section by adding an edge between each pair of nearest degree $2$ vertices.

We are currently unable to explain the overlap between the graphs in our
characterizations of graphs with $2n-4$, $2n-3$, or $2n$ edges that admit two
distinct eigenvalues, and the graphs in the characterizations in [19], [12],
[13], and [21]. It seems reasonable to expect that the maximal graphs whose
compatible matrices have all of their eigenvalues contained in $[-2,2]$ should
have all of their eigenvalues contained in $\\{-2,2\\}$ and hence have
$q$-value $2$. But we do not have a proof of this claim. A complete
explanation of this coincidence may help the investigation of $r$-regular
graphs $G$ with $q(G)=2$ for $r\geq 5$.

######  Problem 6.3.

For a given integer $l\geq 3$, determine whether the maximal graphs that admit
an integer (or similarly constrained) matrix whose eigenvalues are contained
in $[-l,l]$ have $q(G)=2$.

A regular graph $G$ that is neither complete nor empty is _strongly regular_
if there exist constants $a$ and $c$ so that any two adjacent vertices in $G$
have $a$ common neighbors, and any two non-adjacent vertices have $c$ common
neighbors. The definition implies that the diameter of a connected strongly
regular graph is at most $2$. If $G$ is a connected regular graph, then $A(G)$
has three distinct eigenvalues if and only if $G$ is a strongly regular graph
(see, e.g., Lemma 10.2.1 in [11]). So $q(G)\in\\{2,3\\}$ for a strongly
regular graph $G$. In [10], Furst and Grotts show that $L(K_{n})$, the line
graph of $K_{n}$, has $q(L(K_{n}))=2$ for all $n\geq 3$ (note that $L(K_{n})$
is a strongly regular graph for all $n\geq 3$).

A connected graph $G$ is _distance regular_ if there are integers $b_{i}$ and
$c_{i}$ for all $i\geq 0$ so that for any two vertices $u$ and $v$ at distance
$i$ in $G$,

$|N_{1}(v)\cap N_{i+1}(u)|=b_{i}\quad\text{and}\quad|N_{1}(v)\cap
N_{i-1}(u)|=c_{i}.$

(See [9] for an extensive treatment of distance-regular graphs.) Distance-
regular graphs with diameter $2$ are strongly regular. Since Corollary 2.2 and
Theorem 2.4 give a complete characterization of the $r$-regular graphs that
admit two distinct eigenvalues for $r\leq 4$, they also determine the
distance-regular graphs of valency at most $4$ that admit two distinct
eigenvalues. Excluding the complete graphs and complete multipartite graphs in
the list, these are $Q_{3}$, $R_{10,4}$, $R_{14,1}$, and $Q_{4}$. Note that
these graphs all have diameter at least $3$, and thus are not strongly
regular. The closed candles $H_{3}$ and $H_{4}$ are complete multipartite
graphs, and all $H_{k}$ for $k\geq 5$ are not distance regular.

######  Problem 6.4.

Determine the distance-regular graphs $G$ with $q(G)=2$.

We finish with two observations about the $4$-regular graphs $G$ with
$q(G)=2$, and problems they raise. With the exception of $K_{5}$ and
$R_{7,1}$, all of the $4$-regular graphs that appear in Theorem 2.4 have even
order. In particular, if $|V(G)|\geq 8$, then $G$ must have even order.

######  Problem 6.5.

Determine whether for every integer $k$, there is some value $n_{k}$ so that
every $k$-regular graph $G$ with $|V(G)|\geq n_{k}$ and $q(G)=2$ has even
order.

The graphs $H_{k}$ are all circulant graphs, as are some of the sporadic
graphs listed in Theorem 2.4. More broadly, many of the graphs in our
characterization are vertex transitive. It would be interesting to investigate
the highly symmetric graphs that admit a matrix with two distinct eigenvalues.

######  Problem 6.6.

Determine the circulant graphs $G$ that have $q(G)=2$. What can be said about
the automorphism groups of regular graphs with $q(G)=2$?

## Acknowledgements

Shaun M. Fallat was supported in part by an NSERC Discovery Research Grant,
Application No.: RGPIN–2019–03934. Veronika Furst was supported in part by a
Fort Lewis College Faculty Development Grant. Shahla Nasserasr was supported
in part by a Rochester Institute of Technology COS Dean’s Research Initiation
Grant. Brendan Rooney was supported in part by an RIT COS Dean’s Research
Initiation Grant. Michael Tait was supported in part by NSF grant DMS-2011553
and a Villanova University Summer Grant.

This project began as part of the “Inverse Eigenvalue Problems for Graphs and
Zero Forcing” Research Community sponsored by the American Institute of
Mathematics (AIM). We thank AIM for their support, and we thank the organizers
and participants for contributing to this stimulating research experience.

We thank Tracy Hall for the matrix associated with the graph $R_{7,1}$ and
Bryan Shader for the matrices used in the proof of Lemma 2.3.

## References

  * [1] Mohammad Adm, Shaun Fallat, Karen Meagher, Shahla Nasserasr, Sarah Plosker, and Boting Yang.  Achievable multiplicity partitions in the inverse eigenvalue problem of a graph.  Spec. Matrices, 7:276–290, 2019.
  * [2] Bahman Ahmadi, Fatemeh Alinaghipour, Michael S. Cavers, Shaun Fallat, Karen Meagher, and Shahla Nasserasr.  Minimum number of distinct eigenvalues of graphs.  Electron. J. Linear Algebra, 26:673–691, 2013.  Erratum available at: https://journals.uwyo.edu/index.php/ela/article/view/1293/5765.
  * [3] John Ahn, Christine Alar, Beth Bjorkman, Steve Butler, Joshua Carlson, Audrey Goodnight, Haley Knox, Casandra Monroe, and Michael Wigal.  Ordered multiplicity inverse eigenvalue problem for graphs on six vertices.  Electron. J. Linear Algebra, 37:316–358, 2021.
  * [4] R. F. Bailey and R. Craigen.  On orthogonal matrices with zero diagonal.  Electron. J. Linear Algebra, 35:307–318, 2019.
  * [5] Wayne Barrett, Steve Butler, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Bryan L. Shader, and Michael Young.  The inverse eigenvalue problem of a graph: multiplicities and minors.  J. Combin. Theory Ser. B, 142:276–306, 2020.
  * [6] Wayne Barrett, Shaun Fallat, Veronika Furst, Franklin Kenter, Shahla Nasserasr, Brendan Rooney, Michael Tait, and Hein van der Holst.  Sparsity of graphs that allow two distinct eigenvalues.  https://doi.org/10.48550/arXiv.2206.08860, 2022.
  * [7] Wayne Barrett, Shaun Fallat, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, and Bryan L. Shader.  Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph.  Electron. J. Combin., 24(2):Paper No. 2.40, 28, 2017.
  * [8] Beth Bjorkman, Leslie Hogben, Scarlitte Ponce, Carolyn Reinhart, and Theodore Tranel.  Applications of analysis to the determination of the minimum number of distinct eigenvalues of a graph.  Pure Appl. Funct. Anal., 3(4):537–563, 2018.
  * [9] Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier.  Distance-regular graphs.  Springer-Verlag, Berlin, 1989.
  * [10] V. Furst and H. Grotts.  Tight frame graphs arising as line graphs.  PUMP J. Undergrad. Res., 4:1–19, 2021.
  * [11] Chris Godsil and Gordon Royle.  Algebraic graph theory, volume 207 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 2001.
  * [12] Gary Greaves.  Cyclotomic matrices over real quadratic integer rings.  Linear Algebra Appl., 437(9):2252–2261, 2012.
  * [13] Gary Greaves.  Cyclotomic matrices over the Eisenstein and Gaussian integers.  J. Algebra, 372:560–583, 2012.
  * [14] Leslie Hogben, Jephian C.-H. Lin, and Bryan L. Shader.  Inverse problems and zero forcing for graphs, volume 270 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2022.
  * [15] António Leal-Duarte and Charles R. Johnson.  On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree.  Math. Inequal. Appl., 5(2):175–180, 2002.
  * [16] Rupert H. Levene, Polona Oblak, and Helena Šmigoc.  A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph.  Linear Algebra Appl., 564:236–263, 2019.
  * [17] Rupert H. Levene, Polona Oblak, and Helena Šmigoc.  Orthogonal symmetric matrices and joins of graphs, 2020.
  * [18] Brendan D. McKay and Adolfo Piperno.  Practical graph isomorphism, II.  J. Symbolic Comput., 60:94–112, 2014.
  * [19] James McKee and Chris Smyth.  Integer symmetric matrices having all their eigenvalues in the interval $[-2,2]$.  J. Algebra, 317(1):260–290, 2007.
  * [20] OEIS Foundation Inc.  Entry A006820 in The Online Encyclopedia of Integer Sequences, 2023.  Published electronically at https://oeis.org/A006820.
  * [21] Graeme Taylor.  Cyclotomic matrices and graphs over the ring of integers of some imaginary quadratic fields.  J. Algebra, 331:523–545, 2011.