#  Tricyclic graphs with exactly two main eigenvalues ††thanks: This research
was partially supported by the NSF of China(No.10971086).

Xiaoxia Fan, Yanfeng Luo
Department of Mathematics, Lanzhou University,
Lanzhou, Gansu 730000, PR China
<EMAIL_ADDRESS>
###### Abstract

An eigenvalue of a graph $G$ is called a main eigenvalue if it has an
eigenvector the sum of whose entries is not equal to zero. In this paper, all
connected tricyclic graphs with exactly two main eigenvalues are determined.

2000 Mathematics Subject Classification: 05C50

Keywords: Main eigenvalues; Tricyclic graphs; 2-walk $(a,b)$-linear graphs

##  1  Introduction

All graphs considered in this paper are finite, undirected and simple. Let
$G=(V,E)$ be a graph with vertex set $V(G)$ and edge set $E(G)$. Denote by
$A(G)$ the adjacency matrix of $G$. The eigenvalues of $G$ are those of
$A(G)$. An eigenvalue of a graph $G$ is called a main eigenvalue if it has an
eigenvector the sum of whose entries is not equal to zero. It is well known
that a graph is regular if and only if it has exactly one main eigenvalue.

A long-standing problem posed by Cvetkovic ([2]) is that of how to
characterize graphs with exactly $k(k\geq 2)$ main eigenvalues. Hagos [3] gave
an alternative characterization of graphs with exactly two main eigenvalues.
Recently, Hou and Zhou [4] characterized the trees with exactly two main
eigenvalues.

A vertex of a graph $G$ is said to be pendant if it has degree one. Denote by
$C_{n}$ and $P_{n}$ the cycle and path of order $n$, respectively. A connected
graph is said to be tricyclic (resp., unicyclic and bicyclic), if
$|E(G)|=|V(G)|+2$ (resp., $|E(G)|=|V(G)|$ and $|E(G)|=|V(G)|+1$). Hou and Tian
[5] showed that the graphs $C_{r}^{k}$ for some positive integers $k,r$ with
$r\geq 3$, where $C_{r}^{k}$ is the graph obtained from $C_{r}$ by attaching
$k>0$ pendant vertices to every vertex of $C_{r}$, are the only connected
unicyclic graphs with exactly two main eigenvalues. Hu et al. [6] and Shi [7]
characterized all connected bicyclic graphs with exactly two main eigenvalues
independently. This paper will continue the line of this research and
determine all connected tricyclic graphs with exactly two main eigenvalues.

For any tricyclic graph $G$, the base of $G$, denoted by $G_{B}$ is the
minimal tricyclic subgraph of $G$. Clearly, $G_{B}$ is the unique tricyclic
subgraph of $G$ containing no pendent vertex, and $G$ can be obtained from
$G_{B}$ by attaching trees to some vertices of $G_{B}$. It follows from [8]
that there are 8 types of bases for tricyclic graphs, say,
${\mathcal{T}}_{i},i=1,\dots,8$, which are depicted in Fig. 1.

Figure 1:  The 8 types of bases for tricyclic graphs.

##  2 Preliminaries

In this section, we will present some notations and known results which will
be used in the next section. The reader is referred to [1] for any undefined
notation and terminology on graphs in this paper.

Let $G$ be a graph. As usual, we denote by $d(v)=d_{G}(v)$ and $N(v)=N_{G}(v)$
the degree of vertex $v$ and the set of all neighbors of $v$ in $G$. Let

$S(v)=\sum\limits_{u\in N(v)}d(u).$ (2.1)

A graph $G$ is called 2-walk $(a,b)$-linear if there exist unique rational
numbers $a,b$ such that

$S(v)=ad(v)+b$ (2.2)

holds for every vertex $v\in V(G)$.

An internal path of $G$ is a walk $v_{0}v_{1}\dots v_{s}$ such that the
vertices $v_{0},v_{1},\dots,v_{s}$ are distinct, $d(v_{0})>2,d(v_{s})>2$, and
$d(v_{i})=2$ for $0<i<s$. An internal path is called an internal cycle if
$v_{0}=v_{s}$. If $R$ is a path or a cycle of $G$, the length of $R$, denoted
by $l(R)$, is defined as the number of edges of $R$.

###### Lemma 2.1

([3]). A graph $G$ has exactly two main eigenvalues if and only if $G$ is
2-walk $(a,b)$-linear.

###### Lemma 2.2

([5]). Let $G$ be a 2-walk (a,b)-linear graph. Then both $a$ and $b$ are
integers.

###### Lemma 2.3

([6]). Let $G$ be a 2-walk $(a,b)$-linear graph and $v,u$ be two vertices of
$G$ with unequal degree $d(v),d(u)$, respectively. Then

$a=\frac{S(v)-S(u)}{d(v)-d(u)},\ b=\frac{d(u)S(v)-d(v)S(u)}{d(v)-d(u)}.$ (2.3)

In the following, for convenience, we always assume that ${\mathcal{G}}$ is
the set of tricyclic graphs with exactly two main eigenvalues, $x$ is a
pendent vertex of $G$ (if exist). For each $G\in{\mathcal{G}}$, let $G_{0}$ be
the graph obtained from $G$ by deleting all pendent vertices. From the proof
Lemmas 3.1-3.7 in [6], we know that those Lemmas are also hold for tricyclic
graphs. Hence we have the following two Lemmas.

###### Lemma 2.4

Let $G\in{\mathcal{G}}$ and $R=x_{1}x_{2}\dots x_{t}$ be an internal path of
length at least $2$ in $G$. Then $l(R)\leq 3$. In particular, if $l(R)=3$,
then there exists no path $Q=y_{1}y_{2}y_{3}$ in $G$ such that
$d(y_{1})=d(y_{3})=d(x_{1})$ and $d(y_{2})=2$.

###### Lemma 2.5

Let $G\in{\mathcal{G}}$ and $v\in V(G_{0})$. Then

(i) $G_{0}\in{\mathcal{T}}_{i},i=1,\dots,8$ (see Fig. 1);

(ii) $d(v)=d_{G_{0}}(v)$ or $a+b$;

(iii) if $G$ has at least one pendent vertex, then $S(x)=a+b\geq 3$ and $a\geq
2$;

(iv) for a cycle $C=x_{1}x_{2}\dots x_{t}x_{1}$ of $G$ with
$d_{G_{0}}(x_{1})\geq 3$, $d_{G_{0}}(x_{2})=2$, if $G$ has at least one
pendent vertex, then there is an integer $i\in\\{1,2,\dots,t\\}$ such that
$d(x_{i})\neq a+b$.

##  3 Tricyclic graphs with exactly two main eigenvalues

In this section, we will determine all tricyclic graphs with exactly two main
eigenvalues. By Lemma 2.1, it is sufficient to determine all 2-walk
$(a,b)$-linear tricyclic graphs.

###### Lemma 3.1

Let $G\in{\mathcal{G}}$ has at least one pendent vertex and let
$R=x_{1}x_{2}\dots x_{t}$ be an internal path or an internal cycle of length
at least $3$ in $G_{0}$ with $d_{G_{0}}(x_{1})=d_{G_{0}}(x_{t})\in\\{3,4,6\\}$
or $d_{G_{0}}(x_{1})=3,d_{G_{0}}(x_{t})=5$. Then

(i) $d(x_{2})=d(x_{3})=\dots=d(x_{t-1})\in\\{2,a+b\\}$ and
$d(x_{1})=d(x_{t})$;

(ii) if $d(x_{2})=2$, then $l(R)=3$;

(iii) if $R$ is a cycle with $d_{G_{0}}(x_{1})\in\\{3,4,6\\}$, then $l(R)=3$
and $d(x_{2})=d(x_{3})=2$. In particular, if $d_{G_{0}}(x_{1})=3$, then $a=2$;

(iv) if $R$ is a cycle with $d_{G_{0}}(x_{1})=5$, then $l(R)=3$,
$d(x_{2})=d(x_{3})\in\\{2,3\\}$. In particular, if $d(x_{2})=d(x_{3})=3$, then
$d(x_{1})=5$ and $a=3,b=0$.

Proof. (i) By way of contradiction, assume that there is an integer
$i\in\\{2,3,\dots,t-2\\}$ such that $d(x_{i})\neq d(x_{i+1})$. Without loss of
generality, suppose that $i$ is the smallest integer such that $d(x_{i})\neq
d(x_{i+1})$. By Lemma 2.5 (ii), we may assume that $d(x_{i})=2$ and
$d(x_{i+1})=a+b$. Hence $d(x_{2})=d(x_{3})=\dots=d(x_{i})=2$. Applying (2.3)
with $(v,u)=(x_{i+1},x)$, we have

$a=\frac{S(x_{i+1})-S(x)}{d(x_{i+1})-d(x)}=\frac{a+b-2+2+d(x_{i+2})-(a+b))}{a+b-1}=\frac{d(x_{i+2})}{a+b-1}.$

This together with Lemma 2.5 (iii) implies that

$d(x_{i+2})=a(a+b-1)\geq 2(a+b-1)\geq a+b+1>max\\{a+b,3\\}.$ (3.1)

By Lemma 2.5 (ii), we have $d(x_{j})\in\\{a+b,2\\}$ for $2\leq j\leq t-1$.
Thus $x_{i+2}\in\\{x_{1},x_{t}\\}$.

If $d_{G_{0}}(x_{1})=d_{G_{0}}(x_{t})=3$, then
$d(x_{i+2})\in\\{d(x_{1}),d(x_{t})\\}\subseteq\\{3,a+b\\}$, contrary to (3.1).

If $d_{G_{0}}(x_{1})=d_{G_{0}}(x_{t})=4$, then
$d(x_{1}),d(x_{t})\in\\{4,a+b\\}$. It follows from (3.1) that
$d(x_{i+2})=a(a+b-1)=4$. This together with Lemma 2.5 (iii) implies that
$a=2,b=1$. Note that $d(x_{2})=2$. Then $S(x_{2})=5$ by (2.2). On the other
hand, $d_{G_{0}}(x_{1})=4>a+b$, so $d(x_{1})=4$ by Lemma 2.5 (ii). Thus by
(2.1), $S(x_{2})=d(x_{1})+d(x_{3})=4+d(x_{3})>5$, a contradiction.

If $d_{G_{0}}(x_{1})=d_{G_{0}}(x_{t})=6$, with a similar argument of the case
$d_{G_{0}}(x_{1})=d_{G_{0}}(x_{t})=4$, we will get a contradiction again.

If $d_{G_{0}}(x_{1})=3,d_{G_{0}}(x_{t})=5$, then by (3.1)
$d(x_{i+2})=d(x_{t})=d_{G_{0}}(x_{t})=5$ and $a(a+b-1)=5$. It contradicts the
fact that $a\geq 2,a+b\geq 3$.

Hence $d(x_{2})=d(x_{3})=\dots=d(x_{t-1})\in\\{2,a+b\\}$. Therefore
$S(x_{2})=S(x_{t-1})$ by (2.2). On the other hand, by (2.1),
$S(x_{2})=d(x_{2})-2+d(x_{1})+d(x_{3}),S(x_{t-1})=d(x_{t-1})-2+d(x_{t})+d(x_{t-3})$.
It follows that $d(x_{1})=d(x_{t})$.

(ii) Suppose contrary that $l(R)\geq 4$. Then $d(x_{3})=d(x_{4})=2$ by (i).
Applying (2.3) with $(v,u)=(x_{3},x)$, we have $a=4-(a+b)$, which is
impossible by Lemma 2.5 (iii).

(iii) By Lemma 2.5 (ii), we have $d(x_{2})\in\\{2,a+b\\}$. If $d(x_{2})=a+b$,
then $d(x_{i})=a+b$ for $2\leq i\leq t-1$ by (i). Thus
$d(x_{1})=d_{G_{0}}(x_{1})\neq a+b$ by Lemma 2.5 (iv). Applying (2.3) with
$(v,u)=(x_{2},x)$, we have

$a=\frac{a+b-2+d(x_{1})+a+b-(a+b)}{a+b-1}=1+\frac{d(x_{1})-1}{a+b-1}=1+\frac{d_{G_{0}}(x_{1})-1}{a+b-1}.$
(3.2)

Note that $d_{G_{0}}(x_{1})=3,4$ or $6$ and $d_{G_{0}}(x_{1})\neq a+b\geq 3$.
It follows from (3.2) that $a$ can not be an integer. It contradicts Lemma
2.2. Hence $d(x_{2})=2$. Therefore $l(R)=3$ and $d(x_{3})=d(x_{2})=2$.

In particular, if $d_{G_{0}}(x_{1})=3$, then $a=2+d(x_{1})-(a+b)$ by applying
(2.3) with $(v,u)=(x_{2},x)$. If $d(x_{1})=a+b$, then $a=2$. If
$d(x_{1})=d_{G_{0}}(x_{1})=3$, then $a=5-(a+b)$. It follows from Lemmas 2.2
and 2.5 (iii) that $a=2$.

(iv) By Lemma 2.5 (ii), $d(x_{2})\in\\{2,a+b\\}$. If $d(x_{2})=2$, then
$l(R)=3$ and $d(x_{3})=2$ by (i) and (ii). If $d(x_{2})=a+b$, then
$d(x_{i})=a+b$ for $2\leq i\leq t-1$ by (i). So
$d(x_{1})=d_{G_{0}}(x_{1})=5\neq a+b$ by Lemma 2.5 (iv). Applying (2.3) with
$(v,u)=(x_{2},x)$, we have $a=1+\frac{4}{a+b-1}$. Thus $a+b=3$ and $a=3$ by
Lemmas 2.2 and 2.5 (iii). Suppose that $l(R)\geq 4$. Then
$d(x_{2})=d(x_{3})=d(x_{4})=a+b=3$ by (ii). Applying (2.3) with
$(v,u)=(x_{3},x)$, we have $a=2$. It is a contradiction. Therefore $l(R)=3$.
$\square$

Figure 2:  The graphs $T_{i}$ for $i=1,\dots,8$.  Figure 3:  The graphs
$H_{i}$ for i=1,…,30.

###### Lemma 3.2

Let $G\in{\mathcal{G}}$ with $G_{0}\in{\mathcal{T}}_{1}$ (see Fig. 1). Then
$G=H_{i}$ for $i=1,2$ (see Fig. 3).

Proof. If $G_{0}\in{\mathcal{T}}_{1}$, then
$d_{G_{0}}(u_{1}),d_{G_{0}}(v_{1}),d_{G_{0}}(w_{1})\in\\{3,4,5,6\\}$ and so
each cycle of $G_{0}$ has the length of $3$ by Lemmas 2.4 and 3.1. Hence
$G_{0}=T_{1}$ (see Fig. 2), where $n,m,k\geq 1$. For convenience, we set
$w_{k}=v_{m}=u_{n}$.

Case 1. $n=m=k=1$. If $G$ has no pendent vertex, then $G=H_{1}$ (see Fig. 3).
By (2.3), $H_{1}$ is 2-walk $(1,6)$-linear. If $G$ has at least one pendent
vertex, say $x$, then $x\in N(u_{1})$ since $d(x_{i})=2$ for $i=1,\dots,6$ by
Lemma 3.1 (iii). It follows from Lemma 2.5 (ii) that $d(u_{1})=a+b>6$.
Applying (2.3) with $(v,u)=(u_{1},x)$, we have
$a=\frac{a+b-6+12-(a+b)}{a+b-1}<2$. This contradicts Lemma 2.5 (iii).

Case 2. $n\geq 2$. We consider the following two cases:

Subcase 1. $G$ has no pendent vertex. Then $S(x_{1})=2+d(w_{1})=S(x_{5})=5$ by
(2.1) and (2.2). Hence $d(w_{1})=3$. It implies that $k\geq 2$. Similarly, we
have $d(v_{1})=3$ and $m\geq 2$. By Lemma 2.4, we have $n,m,k\in\\{2,4\\}$.
Without loss of generality, suppose that $n\geq m\geq k$. If $n=2$, then
$m=k=2$. Hence $S(u_{1})=7,S(u_{2})=9$ by (2.1). On the other hand,
$d(u_{1})=d(u_{2})=3$, so $S(u_{1})=S(u_{2})$ by (2.2), a contradiction. Hence
$n=4$. Similarly, we have $m=k=4$. Therefore $G=H_{2}$ (see Fig. 3). By (2.3),
$H_{2}$ is 2-walk $(1,3)$-linear.

Subcase 2. $G$ has at least one pendent vertex. In this case, we show that
there is no such graph with exactly two main eigenvalues. Since
$d_{G_{0}}(u_{1})=3$, we have $a=2$ by Lemma 3.1 (iii). So $d(x_{i})=2$ for
$i=1,\dots,6$ by Lemma 3.1 (iii) and (iv).

We claim that $m,k\geq 2$. Otherwise, let $k=1$. Then
$S(x_{1})=2+d(w_{1})=S(x_{5})=2+d(u_{1})$ by (2.1) and (2.2). It follows from
Lemma 2.5 (ii) and the fact that $d_{G_{0}}(u_{1})\neq d_{G_{0}}(w_{1})$ that
$d(w_{1})=d(u_{1})=a+b$. Hence $S(u_{1})=S(w_{1})$ by (2.2). By (2.1),

$S(u_{1})=a+b-3+4+d(u_{2}),S(w_{1})=\Big{\\{}\begin{array}[]{ll}a+b-5+8+d(u_{n-1}),&\mbox{if}~{}m=1,\\\
a+b-4+4+d(v_{m-1})+d(u_{n-1}),&\mbox{if}~{}m\geq 2.\\\ \end{array}$

If $m=1$, then $d(u_{2})=d(u_{n-1})+2$. This is impossible by Lemma 3.1 (i).
If $m\geq 2$, then $d(u_{2})+1=d(v_{m-1})+d(u_{n-1})$. Obviously,
$u_{2}=u_{n-1}$ when $n=3$ and $d(u_{2})=d(u_{n-1})$ when $n\geq 4$ by Lemma
3.1 (i). Hence $d(v_{m-1})=1$, it contradicts the fact that $d(v_{m-1})\geq
d_{G_{0}}(v_{m-1})=2$. Therefore $k\geq 2$. Dually, we have $m\geq 2$.

Note that $d(x_{1})=d(x_{3})=d(x_{5})$, we have
$S(x_{1})=2+d(w_{1})=S(x_{3})=2+d(v_{1})=S(x_{5})=2+d(u_{1})$ by (2.1) and
(2.2). It implies that $d(w_{1})=d(v_{1})=d(u_{1})=3$ or $a+b$.

If $d(u_{1})=3$. Applying (2.3) with $(v,u)=(x_{5},x)$, we have $a=5-(a+b)$.
So $a=2,b=1$. Furthermore, $S(u_{1})=4+d(u_{2})=7$ by (2.1) and (2.2). Thus
$d(u_{2})=3$. It follows from Lemma 3.1 (i) that $d(u_{i})=3$ for $2\leq i\leq
n-1$. Similarly, we have $d(v_{i})=d(w_{j})=3$ for $2\leq i\leq m-1$ and
$2\leq j\leq k-1$. Note that $d_{G_{0}}(u_{n})=a+b=3$. We have $d(u_{n})=3$
and $S(u_{n})=7$ by (2.2). On the other hand, $S(u_{n})=9$ by (2.1), a
contradiction.

If $d(u_{1})=a+b\neq 3$, then $a+b\geq 4$ by Lemma 2.5 (iii). Applying (2.3)
with $(v,u)=(u_{1},x)$, we have $2=\frac{a+b-3+4+d(u_{2})-(a+b)}{a+b-1}$. Note
that $d_{G_{0}}(u_{2})=2$ or $3$, we have
$d(u_{2})=2(a+b)-3>max\\{a+b,d_{G_{0}}(u_{2})\\}$. It contradicts Lemma 2.5
(ii). $\square$

Figure 4:  The graphs ${\mathcal{G}}_{i}$ for i=1,…,8, where $l_{1},b\geq 1$
and $max\\{k_{1},k_{2}\\}\geq 1$

###### Lemma 3.3

Let $G\in{\mathcal{G}}$ with $G_{0}\in{\mathcal{T}}_{2}$ (see Fig. 1). Then
$G=H_{i}$ for $i=3,4,5,6$ (see Fig. 3) or $G\in{\mathcal{G}}_{j}$ for $j=1,2$
(see Fig. 4).

Proof. If $G_{0}\in{\mathcal{T}}_{2}$, then
$d_{G_{0}}(w_{1}),d_{G_{0}}(r_{1})\in\\{3,4\\}$ and so each cycle of $G_{0}$
has the length of $3$ by Lemmas 2.4 and 3.1 (iii). Hence $G_{0}=T_{2}$ and
$d(x_{i})=2$ for $i=1,\dots,4$ (see Fig. 2), where $k,l\geq 1,n,m\geq 2$. For
convenience, we set $w_{k}=v_{1}=u_{1}$ and $v_{m}=u_{n}=r_{l}$. By (2.1) and
(2.2), $S(x_{1})=2+d(w_{1})=S(x_{3})=2+d(r_{1})$. Hence $d(w_{1})=d(r_{1})$.

If $G$ has no pendent vertex, then $k,l\in\\{1,2,4\\}$ and $m,n\in\\{2,4\\}$
by Lemma 2.4.

First, let $k=1$. Then $d(w_{1})=d(r_{1})=4$. So $l=1$. Therefore $G=H_{i}$
for $i=3,4$ (see Fig. 3). By (2.3), $H_{3}$ and $H_{4}$ are 2-walk
$(2,2)$-linear and 2-walk $(1,4)$-linear, respectively.

Next, let $k=2$. Then $d(w_{1})=d(r_{1})=3$. By (2.1) and (2.2),
$S(r_{1})=4+d(r_{2})=S(w_{1})=7$. So $d(r_{2})=3$ and $l=2$. Similarly,
$S(u_{1})=3+d(u_{2})+d(v_{2})=S(w_{1})=7$. So $d(u_{2})=d(v_{2})=2$. Note that
$n,m=2$ or $4$, we have $n=m=4$ and $d(u_{3})=d(v_{3})=2$. Therefore,
$G=H_{5}$ (see Fig. 3). By (2.3), $H_{5}$ is 2-walk (2,1)-linear.

Finally, let $k=4$. With a similar argument of the case $k=2$, we have
$G=H_{6}$ is 2-walk (1,3)-linear (see Fig. 3).

If $G$ has at least one pendent vertex. We consider the following two cases:

Case 1. $k=l=1$. Then $d(w_{1})=d(r_{1})=4$ or $a+b$ by Lemma 2.5 (ii).

If $d(w_{1})=4$. Applying (2.3) with $(v,u)=(x_{1},x)$, we have $a=6-(a+b)$.
It follows from Lemmas 2.2 and 2.5 (iii) that $a+b=3$ or $4$.

If $a+b=3$, then $a=3,b=0$. So $S(w_{1})=4+d(u_{2})+d(v_{2})=12$ by (2.1) and
(2.2). By Lemma 2.5 (ii), $d(u_{2}),d(v_{2})\in\\{2,4,a+b\\}$. Thus
$d(u_{2})=d(v_{2})=4$. It implies that $n=m=2$, which is impossible since $G$
is simple.

If $a+b=4$, then $a=b=2$. So $S(w_{1})=4+d(u_{2})+d(v_{2})=10$ by (2.1) and
(2.2). By Lemma 2.5 (ii), $d(u_{2}),d(v_{2})\in\\{2,4\\}$. Without loss of
generality, suppose that $d(u_{2})=2,d(v_{2})=4$. Then $d(v_{i})=4$ for $2\leq
i\leq m-1$ by Lemma 3.1 (i). For the vertex $u_{2}$, $S(u_{2})=4+d(u_{3})=6$
by (2.1) and (2.2). So $d(u_{3})=2$. Thus $n\geq 4$. Hence $n=4$ by Lemma 3.1
(ii). Therefore $G\in{\mathcal{G}}_{1}$ (see Fig. 4), where $l_{1}\geq 1$. It
is easy to see that any graph $G\in{\mathcal{G}}_{1}$ is 2-walk
$(2,2)$-linear.

If $d(w_{1})=a+b>d_{G_{0}}(u_{1})=4$. In this case, we show that there is no
such graph with exactly two main eigenvalues. Applying (2.3) with
$(v,u)=(x_{1},x)$ and $(v,u)=(w_{1},x)$, respectively. We have $a=2$ and
$a=\frac{a+b-4+4+d(u_{2})+d(v_{2})-(a+b)}{a+b-1}$, respectively. Hence
$d(u_{2})+d(v_{2})=2(a+b)-2$. By Lemma 2.5 (ii) and the fact that
$d(u_{n})=d(r_{1})=d(w_{1})=a+b$, we have $d(u_{2}),d(v_{2})\in\\{2,a+b\\}$.

If $d(u_{2})=2,d(v_{2})\in\\{2,a+b\\}$ or $d(u_{2})=a+b,d(u_{2})=2$, then
$a+b=3$ or $4$. It contradicts the fact that $a+b>4$.

If $d(u_{2})=d(v_{2})=a+b$, then $2(a+b)-2=2(a+b)$, a contradiction.

Case 2. $k\geq 2$. Then $a=2$ by Lemma 3.1 (iii). By Lemmas 2.5 (ii),
$d(w_{1})=d(r_{1})=3$ or $a+b$.

We first show that $d(w_{1})=d(r_{1})=3$. Otherwise, let
$d(w_{1})=d(r_{1})=a+b\neq 3$. Then $a+b\geq 4$ by Lemma 2.5 (iii). Applying
(2.3) with $(v,u)=(w_{1},x)$, we have
$2=\frac{a+b-3+4+d(w_{2})-(a+b)}{a+b-1}$. Note that $a+b\geq 4$ and
$d_{G_{0}}(w_{2})=2$ or $3$. We have
$d(w_{2})=2(a+b)-3>max\\{a+b,d_{G_{0}}(w_{2})\\}$. It contradicts Lemma 2.5
(ii). Hence $d(w_{1})=d(r_{1})=3$. It implies that $l\geq 2$.

Next, applying (2.3) with $(v,u)=(x_{1},x)$, we have $a=5-(a+b)$. So $a+b=3$
and $a=2,b=1$. For the vertex $w_{1}$, $S(w_{1})=4+d(w_{2})=7$ by (2.1) and
(2.2). So $d(w_{2})=3$. Thus $d(w_{i})=3$ for $2\leq i\leq k-1$ by Lemma 3.1
(i). Note that $d_{G_{0}}(w_{k})=3$. We have $d(w_{k})=3$ by Lemma 2.5 (ii).
Hence $d(w_{i})=3$ for $1\leq i\leq k$.

Similarly, we have $d(r_{j})=3$ for $1\leq j\leq l$.

For the vertex $w_{k}$, $S(w_{k})=3+d(u_{2})+d(v_{2})=7$. Note that
$d(u_{2}),d(v_{2})\in\\{2,3\\}$ by Lemma 2.5 (ii). We have
$d(u_{2})=d(v_{2})=2$. It follows from Lemmas 2.4 and 3.1 that $m=n=4$ and
$d(u_{3})=d(v_{3})=2$.

Therefore $G\in{\mathcal{G}}_{2}$ (see Fig. 4), where
$max\\{k_{1},k_{2}\\}\geq 1$. It is easy to see that any graph
$G\in{\mathcal{G}}_{2}$ is 2-walk (2,1)-linear. $\square$

###### Lemma 3.4

Let $G\in{\mathcal{G}}$ with $G_{0}\in{\mathcal{T}}_{3}$ (see Fig. 1). Then
$G=H_{7}$ (see Fig. 3).

Proof. If $G_{0}\in{\mathcal{T}}_{3}$, then $d_{G_{0}}(r_{1})\in\\{3,5\\}$ and
so the cycle of $G_{0}$ has the length of $3$ by Lemmas 2.4 and 3.1. Hence
$G_{0}=T_{3}$ (see Fig. 2), where $n,m,k\geq 2,l\geq 1$. For convenience, we
set $u_{1}=v_{1}=w_{1}$ and $u_{n}=v_{m}=w_{k}=r_{l}$.

We first show that $G$ contains at least one pendent vertex. On the contrary,
suppose that $G$ has no pendent vertex. Then $n,m,k,l\leq 4$ by Lemma 2.4.
Without loss of generality, suppose that $n\geq m\geq k$. If $l=1$, then
$S(x_{1})=7$ and $S(u_{2})=5$ or $8$ by (2.1). So $S(u_{2})\neq S(x_{1})$. On
the other hand, $S(u_{2})=S(x_{1})$ by (2.2), a contradiction. If $l\geq 2$,
then $d(u_{n})=4,d(r_{1})=3$. So $S(x_{1})=5$ and $S(u_{n-1})=6$ or $7$ by
(2.1). On the other hand, $S(x_{1})=S(u_{n-1})$ by (2.2), a contradiction.
Therefore, $G$ has at least one pendent vertex. We consider the following two
cases:

Case 1. $l=1$. By Lemma 3.1 (iv), $d(x_{1})=d(x_{2})=3$ or
$d(x_{1})=d(x_{2})=2$.

If $d(x_{1})=d(x_{2})=3$, then $a=3,b=0,d(u_{n})=5$ by Lemma 3.1 (iv). So
$d(u_{1})=3\neq d(u_{n})$ by Lemma 2.5 (ii). It follows from Lemma 3.1 (i)
that $n,m,k\leq 3$. Without loss of generality, suppose that $n=m=3,k=2$ or
$3$. Then $S(u_{3})=6+d(u_{2})+d(v_{2})+d(w_{k-1})=15$ by (2.1) and (2.2).
Note that $d(u_{2}),d(v_{2}),d(w_{k-1})=2$ or $3$ by Lemma 2.5 (ii). We have
$d(u_{2})=d(v_{2})=d(w_{k-1})=3$. So $S(u_{1})=6+d(w_{2})=9$ by (2.1) and
(2.2). Thus $d(w_{2})=3$. It implies that $k=3$. Therefore $G=H_{7}$ (see Fig.
3). By (2.3), $H_{7}$ is 2-walk $(3,0)$-linear.

If $d(x_{1})=d(x_{2})=2$. We show that in this case there is no such graph
with exactly two main eigenvalues. We consider the following two cases:

Subcase 1. $max\\{n,m,k\\}\geq 4$. Without loss of generality, suppose that
$n\geq 4$. Then $d(u_{1})=d(u_{n})$ and $d(u_{i})=d(u_{2})$ for $2\leq i\leq
n-1$ by Lemma 3.1 (i). Note that $d_{G_{0}}(u_{1})\neq d_{G_{0}}(u_{n})$. We
have $d(u_{1})=d(u_{n})=a+b\geq d_{G_{0}}(u_{n})=5$ by Lemma 2.5 (ii). Hence

$S(u_{1})=a+b-3+d(u_{2})+d(v_{2})+d(w_{2}),\
S(u_{n})=a+b-5+4+d(u_{n-1})+d(v_{m-1})+d(w_{k-1}).$

We next show that $d(v_{2})=d(v_{m-1})$. If $m=2$, then $v_{2}=u_{n}$,
$v_{m-1}=u_{1}$. So $d(v_{2})=d(u_{n})=d(u_{1})=d(v_{m-1})$. If $m=3$,
clearly, $d(v_{2})=d(v_{m-1})$. If $m\geq 4$, then $d(v_{2})=d(v_{m-1})$ by
Lemma 3.1 (i). Therefore $d(v_{2})=d(v_{m-1})$ for all $m\geq 2$.

Similarly, we have $d(w_{2})=d(w_{k-1})$ for all $k\geq 2$. Hence
$S(u_{1})\neq S(u_{n})$. On the other hand, $S(u_{1})=S(u_{n})$ by (2.2), a
contradiction.

Subcase 2. $max\\{n,m,k\\}\leq 3$. Without loss of generality, suppose that
$n=m=3$ and $k=2$ or $3$. We claim that $d(u_{2})=a+b$. Otherwise, let
$d(u_{2})=d_{G_{0}}(u_{2})=2$. Then
$d(u_{1})+d(u_{3})=S(u_{2})=S(x_{1})=2+d(u_{3})$ by (2.1) and (2.2), which is
impossible since $d(u_{1})\geq d_{G_{0}}(u_{1})=3$. Hence $d(u_{2})=a+b$.
Similarly, we have $d(v_{2})=a+b$.

Note that $d(u_{3})\in\\{a+b,5\\}$ by Lemma 2.5 (ii). We consider the
following two cases:

If $d(u_{3})=a+b\geq d_{G_{0}}(u_{3})=5$. Applying Lemma 2.5 (iv) with
$C=u_{1}u_{2}u_{3}v_{2}u_{1}$, we have $d(u_{1})\neq a+b$. So $d(u_{1})=3$.
Applying (2.3) with $(v,u)=(u_{1},x)$ and $(v,u)=(x_{1},x)$, respectively. We
have $a=\frac{a+b+d(w_{2})}{2}$ and $a=2$, respectively. Hence
$d(w_{2})=4-(a+b)<0$, a contradiction.

If $d(u_{3})=d_{G_{0}}(u_{3})=5\neq a+b$, then $a=7-(a+b)$ by applying (2.3)
with $(v,u)=(x_{1},x)$. It follows from Lemma 2.5 (iii) that $a+b=3$ or $4$.
If $a+b=3$, then $a=4,b=-1$. Hence $S(u_{2})=d(u_{1})+6=11$ by (2.1) and
(2.2). This is impossible since $d(u_{1})=3$ by Lemma 2.5 (ii). If $a+b=4$,
then $a=3,b=1$. Thus $S(u_{2})=d(u_{1})+7=13$ by (2.1) and (2.2). This is also
impossible since $d(u_{1})=3$ or $4$.

Case 2. $l\geq 2$. We show that in this case there is no such graph with
exactly two main eigenvalues. By Lemma 3.1 (iii), we have $a=2$ and
$d(x_{1})=d(x_{2})=2$. Applying (2.3) with $(v,u)=(x_{1},x)$, we have
$2=2+d(r_{1})-(a+b)$. So $d(r_{1})=a+b$. Applying (2.3) with
$(v,u)=(r_{1},x)$, we have $2=\frac{a+b-3+4+d(r_{2})-(a+b)}{a+b-1}$. Hence
$d(r_{2})=2(a+b)-3$. By Lemma 2.5 (ii), $d(r_{2})\in\\{2,4,a+b\\}$.

If $d(r_{2})=2$ or $4$, then $a+b$ is not an integer, a contradiction.

If $d(r_{2})=a+b$, then $a+b=3$. So $a=2,b=1$. By Lemmas 2.5 (ii) and 3.1 (i),
we have $d(r_{l})=4$ and $d(r_{l-1})=d(r_{2})=3$. Hence
$S(r_{l})=3+d(u_{n-1})+d(w_{k-1})+d(v_{m-1})=9$ by (2.1) and (2.2). It follows
that $d(u_{n-1})=d(w_{k-1})=d(v_{m-1})=2$. Thus $S(u_{n-1})=5$ by (2.2). On
the other hand, $S(u_{n-1})=4+d(u_{n-2})\geq 6$ by (2.1), a contradiction.
$\square$

###### Lemma 3.5

Let $G\in{\mathcal{G}}$ with $G_{0}\in{\mathcal{T}}_{4}$ (see Fig. 1). Then
$G=H_{i}$ for $i=8,9,10$ (see Fig. 3) or $G\in{\mathcal{G}}_{3}$ (see Fig. 4).

Proof. If $G_{0}\in{\mathcal{T}}_{4}$, then $d_{G_{0}}(w_{1})\in\\{3,4\\}$ and
so the cycle of $G_{0}$ has the length of $3$ by Lemmas 2.4 and 3.1 (iii).
Hence $G_{0}=T_{4}$ (see Fig. 2), where $k\geq 1$ and $p,q,n,m\geq 2$. For
convenience, we set $u_{1}=v_{1}=s_{1},u_{n}=v_{m}=t_{1}$ and
$s_{p}=t_{q}=w_{k}$.

If $G$ has no pendent vertex. Without loss of generality, we may assume that
$n\geq m,p\geq q$ and consider the following two cases:

Case 1. $k=1$. Then $S(x_{1})=6$ by (2.1). We claim that $p=2$. Otherwise, let
$p\geq 3$. Then $d(s_{2})=2$ and $S(s_{2})=5$ or $7$ by (2.1). So
$S(x_{1})\neq S(s_{2})$. On the other hand, $S(x_{1})=S(s_{2})$ by (2.2), a
contradiction. Hence $p=2$. Similarly, we have $q=2,n=3,m=2$ or $3$. If $m=2$,
then applying (2.3) with $(v,u)=(w_{1},u_{2})$ and $(v,u)=(w_{1},u_{1})$,
respectively, we have $a=2$ and $a=1$, respectively. A contradiction. If
$m=3$, then $G=H_{8}$ (see Fig. 3). By (2.3), $H_{8}$ is 2-walk
$(2,2)$-linear.

Case 2. $k>1$. By Lemma 2.4, we have $k,p,q,m,n=2$ or $4$.

If $k=2$, then $S(w_{1})=7=S(w_{2})=3+d(s_{p-1})+d(t_{q-1})$ by (2.1) and
(2.2). So $d(s_{2})=d(t_{2})=2$. It implies that $p=q=4$. Hence $n=4,m=2$.
Otherwise, let $m=n=4$. Then $S(u_{1})=6\neq S(w_{1})=7$ by (2.1). On the
other hand, $S(u_{1})=S(w_{1})$ by (2.2), a contradiction. Therefore $n=4,m=2$
and $G=H_{9}$ (see Fig. 3). By (2.3), $H_{9}$ is 2-walk $(2,1)$-linear.

If $k=4$, with a similar argument, we have $G=H_{10}$ is 2-walk $(1,3)$-linear
(see Fig. 3).

If $G$ has at least one pendent vertex, then $k>1$. Otherwise, suppose that
$k=1$. Then $d(w_{1})=4$ or $a+b$ by Lemma 2.5 (ii).

If $d(w_{1})=4\neq a+b$. Applying (2.3) with $(v,u)=(x_{1},x)$, we have
$a=6-(a+b)$. It follows from Lemma 2.5 (iii) that $a=3,b=0$. So
$S(w_{1})=4+d(s_{p-1})+d(t_{q-1})=12$ by (2.1) and (2.2). This is impossible
since $d(s_{p-1}),d(t_{q-1})=2$ or $3$ by Lemma 2.5 (ii).

If $d(w_{1})=a+b\geq 4$. Applying (2.3) with $(v,u)=(x_{1},x)$ and
$(v,u)=(w_{1},x)$, respectively, we have $a=2$ and
$a=\frac{a+b-4+4+d(t_{q-1})+d(s_{p-1})-(a+b)}{a+b-1}$, respectively. Thus

$d(t_{q-1})+d(s_{p-1})=2(a+b)-2.$ (3.3)

Note that $d(t_{q-1}),d(s_{p-1})\in\\{2,3,a+b\\}$. We consider the following
five cases by symmetry:

If $d(t_{q-1})=d(s_{p-1})=2$, then $a+b=3$. This contradicts the fact that
$a+b\geq 4$.

If $d(t_{q-1})=2,d(s_{p-1})=3$, then $a+b=3.5$. This contradicts Lemma 2.2.

If $d(t_{q-1})=2,d(s_{p-1})=a+b$, then $a+b=4$ by (3.3). Note that $a=2$. We
have $b=2$ and $d(s_{p-1})=d(w_{1})=4$. By Lemma 3.1, $d(s_{i})=4$ for $2\leq
i\leq p-1$. So $S(s_{2})=6+d(u_{1})=10$ by (2.1) and (2.2). Thus $d(u_{1})=4$.
Similarly, we have $d(u_{n})=4$. By (2.1) and (2.2),
$S(u_{1})=5+d(u_{2})+d(v_{2})=10$. This is impossible since
$d(u_{2}),d(v_{2})=2$ or $4$.

If $d(t_{q-1})=3,d(s_{p-1})=a+b$, then $a+b=5$ by (3.3). Recall that $a=2$, we
have $b=3$ and $d(w_{1})=5$. Note that $d(t_{q-1})=3\neq a+b$. We have $q=2$.
Thus $S(t_{q-1})=9=5+d(u_{n-1})+d(v_{n-1})$ by (2.1) and (2.2). By Lemma 2.5
(ii), $d(u_{n-1}),d(v_{n-1})\in\\{2,3,5\\}$. Hence $d(u_{n-1})=d(v_{n-1})=2$.
Therefore $S(u_{n-1})=3+d(u_{n-2})=7$, which is impossible since
$d(u_{n-2})\in\\{2,3,5\\}$.

If $d(t_{q-1})=d(s_{p-1})=a+b$, then $2(a+b)=2(a+b)-2$ by (3.3), a
contradiction.

Hence $k>1$. It follows from Lemma 3.1 (iii) that $a=2$ and
$d(x_{1})=d(x_{2})=2$.

Applying (2.3) with $(v,u)=(x_{1},x)$, we have $2=2+d(w_{1})-(a+b)$. So
$d(w_{1})=a+b$. Applying (2.3) with $(v,u)=(w_{1},x)$, we have
$2=\frac{a+b-3+4+d(w_{2})-(a+b)}{a+b-1}$. Thus $d(w_{2})=2(a+b)-3\geq 3$. Note
that $d(w_{2})\in\\{2,3,a+b\\}$ by Lemma 2.5 (ii). We have $d(w_{2})=3$ or
$a+b$. It follows that $a+b=3$ and $a=2,b=1$.

By Lemma 3.1 (i), $d(w_{i})=d(w_{2})=3$ for $2\leq i\leq k-1$.

By Lemma 2.5 (ii), $d(w_{1})=d(w_{k})=d(u_{1})=d(u_{n})=3$.

For the vertex $w_{k}$, we have $S(w_{k})=3+d(s_{p-1})+d(t_{q-1})=7$. It
follows from Lemma 2.5 (ii) that $d(s_{p-1})=d(t_{q-1})=2$ and $p,q\geq 3$.
Hence $p=q=4$ and $d(s_{2})=d(t_{2})=2$ by Lemmas 2.4 and 3.1 (ii).

For the vertex $u_{1}$, we have $S(u_{1})=2+d(v_{2})+d(u_{2})=7$. Note that
$d(u_{2}),d(v_{2})\in\\{2,3\\}$. We may assume that $d(v_{2})=2,d(u_{2})=3$ by
symmetry. It follows from Lemmas 2.4 and 3.1 (ii) that $m=4,d(v_{3})=2$ and
$d(u_{i})=3$ for $2\leq i\leq n-1$.

Therefore $G\in{\mathcal{G}}_{3}$ (see Fig. 4), where
$max\\{k_{1},k_{2}\\}\geq 1$. It is easy to see that any graph
$G\in{\mathcal{G}}_{3}$ is 2-walk $(2,1)$-linear.

Up to now, we complete the proof of the Lemma. $\square$

###### Lemma 3.6

There is no graph $G\in{\mathcal{G}}$ with $G_{0}\in{\mathcal{T}}_{5}$ (see
Fig. 1).

Proof. By way of contradiction, suppose that $G\in{\mathcal{G}}$ with
$G_{0}\in{\mathcal{T}}_{5}$. Let $G_{0}=T_{5}$ (see Fig. 2), where
$n,m,k,p,q\geq 2$. For convenience, we set
$u_{1}=v_{1}=s_{1},u_{n}=w_{k}=t_{q},v_{m}=s_{p}=w_{1}=t_{1}$ and consider the
following two cases:

Case 1. There is a vertex $v\in\\{v_{m-1},s_{p-1},w_{2},t_{2}\\}$ such that
$d_{G_{0}}(v)=2$ and $d(v)=a+b$. Without loss of generality, let $v=v_{m-1}$.
Then $d(v_{i})=a+b$ for $2\leq i\leq m-1$ by Lemma 3.1 (i). In particular,
$a\geq 2,a+b\geq 3$ by Lemma 2.5 (iii). We first show that
$d(u_{1})=d(w_{1})=a+b$.

If $m\geq 4$, then $d(u_{1})=d(w_{1})$ by Lemma 3.1 (i). Note that
$d_{G_{0}}(u_{1})\neq d_{G_{0}}(w_{1})$. We have $d(u_{1})=d(w_{1})=a+b$ by
Lemma 2.5 (ii).

If $m=3$. Applying (2.3) with $(v,u)=(v_{2},x)$, we have

$a=\frac{a+b-2+d(u_{1})+d(w_{1})-(a+b)}{a+b-1}=\frac{d(u_{1})+d(w_{1})-2}{a+b-1}.$

By Lemma 2.5 (ii), $d(u_{1})=3$ or $a+b$ and $d(w_{1})=4$ or $a+b$.

If $d(u_{1})=3,d(w_{1})=4$, then $a=\frac{5}{a+b-1}$. Note that $a\geq 2$ is
an integer. We have $a+b=2$. It contradicts the fact that $a+b\geq 3$.

If $d(u_{1})=3,d(w_{1})=a+b\geq 4$, then $a=1+\frac{2}{a+b-1}<2$, a
contradiction.

If $d(u_{1})=a+b\geq 3,d(w_{1})=4\neq a+b$, then $a=1+\frac{3}{a+b-1}$ is not
an integer, a contradiction.

Hence $d(u_{1})=d(w_{1})=a+b$.

Applying Lemma 2.5 (iv) with $C=u_{1}v_{2}\dots v_{m-1}w_{1}s_{p-1}\dots
s_{2}u_{1}$, we have $p\geq 3$ and $d(s_{i})\neq a+b$ for some $2\leq i\leq
p-1$. It follows from Lemmas 2.5 (ii) and 3.1 (i) that $d(s_{i})=2$ for $2\leq
i\leq p-1$. Applying (2.3) with $(v,u)=(v_{2},x)$ and $(v,u)=(u_{1},x)$,
respectively. We have $a=2$ and $a=1+\frac{d(u_{2})}{a+b-1}$, respectively.
This together with Lemma 2.5 (ii) and the fact that $a+b\geq
d_{G_{0}}(w_{1})=4$ implies that $d(u_{2})=a+b-1=d_{G_{0}}(u_{2})\geq 3$.
Hence $n=2,d(u_{2})=d_{G_{0}}(u_{2})=3$. Therefore $a+b=4$ and $a=b=2$. By
(2.1) and (2.2), $S(u_{2})=4+d(w_{k-1})+d(t_{q-1})=8$. By Lemma 2.5 (ii),
$d(w_{k-1}),d(t_{q-1})=2$ or $4$. Thus $d(w_{k-1})=d(t_{q-1})=2$. Hence
$S(w_{k-1})=3+d(w_{k-2})=6$ by (2.1) and (2.2), which is impossible since
$d(w_{k-2})=2$ or $4$.

Case 2. For any vertex $v\in\\{v_{m-1},s_{p-1},w_{2},t_{2}\\}$, we have
$d_{G_{0}}(v)=3$ or $d(v)=2$. It follows from Lemma 2.4 that $m,k,p,q\leq 4$.
Without loss of generality, suppose that $m\geq p,k\geq q$. Hence $m,k=3$ or
$4$.

Subcase 1. $max\\{m,k\\}=4$. Without loss of generality, suppose that $m=4$.
Then $d(u_{1})=d(w_{1})$ by Lemma 3.1 (i). Note that $d_{G_{0}}(u_{1})\neq
d_{G_{0}}(w_{1})$. We have $d(u_{1})=d(w_{1})=a+b\geq d_{G_{0}}(w_{1})=4$ by
Lemma 2.5 (ii). Thus $G$ has at least one pendent vertex. Applying (2.3) with
$(v,u)=(v_{2},x)$ and $(v,u)=(u_{1},x)$, respectively. We have $a=2$ and
$a=\frac{a+b-3+2+d(s_{2})+d(u_{2})-(a+b)}{a+b-1}$, respectively. Hence
$d(s_{2})+d(u_{2})=2(a+b)-1$.

If $p>2$, then $d(s_{2})=2$. It follows from the fact that
$d_{G_{0}}(u_{2})=2$ or $3$ and $a+b\geq 4$ that
$d(u_{2})=2(a+b)-3>max\\{a+b,d_{G_{0}}(u_{2})\\}$, which is impossible by
Lemma 2.5 (ii).

If $p=2$, then $d(s_{2})=d(w_{1})=a+b$. So $d(u_{2})=a+b-1\geq 3$. It follows
that $n=2,d(u_{2})=d_{G_{0}}(u_{2})=3$ and $a+b=4$. Hence $a=b=2$. By (2.2),
$S(w_{k-1})=6$. On the other hand, $S(w_{k-1})=d(w_{k-2})+d(u_{2})=5$ or $7$
by (2.1), a contradiction.

Subcase 2. $m=k=3$. Then
$d(w_{1})+d(u_{1})=S(v_{2})=S(w_{2})=d(w_{1})+d(u_{n})$ by (2.1) and (2.2). So
$d(u_{1})=d(u_{n})$. Thus $S(u_{1})=S(u_{n})$ by (2.2).

We claim that $p=q=2$ or $3$. Otherwise, let $p\neq q$. Without loss of
generality, suppose that $p=3,q=2$. Then $S(u_{1})=d(u_{1})-3+4+d(u_{2})$ and
$S(u_{n})=d(u_{n})-3+2+d(w_{1})+d(u_{n-1})$. Note that
$d(u_{2})=d(u_{n-1}),d(w_{1})>2$. We have $S(u_{1})\neq S(u_{n})$, a
contradiction. Hence $p=q=2$ or $3$. We consider the following two cases:

Subcase 2.1. $G$ has no pendent vertex. Then $n=2$. Otherwise, suppose that
$n>2$. Then $d(u_{2})=d(v_{2})=2$. By (2.1) and (2.2),
$3+d(u_{3})=S(u_{2})=S(v_{2})=7$. This is impossible since $d(u_{3})=2$ or
$3$. Hence $n=2$. If $p=q=2$. Applying (2.3) with $(v,u)=(u_{1},v_{2})$ and
$(v,u)=(w_{1},u_{1})$, respectively. We have $a=2$ and $a=1$, respectively. A
contradiction. If $p=q=3$, also applying (2.3) with $(v,u)=(u_{1},v_{2})$ and
$(v,u)=(w_{1},u_{1})$, respectively, we have $a=0$ and $a=1$, respectively.
Also a contradiction.

Subcase 2.2. $G$ has at least one pendent vertex. Then $a\geq 2,a+b\geq 3$.

First, let $p=q=3$. Applying (2.3) with $(v,u)=(w_{1},x)$, we have
$a=\frac{d(w_{1})-4+8-(a+b)}{d(w_{1})-1}$. By Lemma 2.5 (ii), $d(w_{1})=a+b$
or $4$. It follows that $a<2$, a contradiction.

Next, suppose that $p=q=2$. By Lemma 2.5 (ii), $d(w_{1})=a+b$ or $4$.

If $d(w_{1})=a+b\geq 4$. Applying (2.3) with $(v,u)=(w_{1},x)$ and note that
$d(u_{1})=d(u_{n})$, we have $a=\frac{2d(u_{1})}{a+b-1}$. If $d(u_{1})=a+b$,
then $a=2+\frac{2}{a+b-1}$ is not an integer, which is impossible by Lemma
2.2. If $d(u_{1})=d_{G_{0}}(u_{1})=3\neq a+b$, then $a+b=4$ and $a=b=2$. So
$S(v_{2})=6$ by (2.2). On the other hand, $S(v_{2})=d(u_{1})+d(w_{1})=7$ by
(2.1), a contradiction.

If $d(w_{1})=4\neq a+b$. Applying (2.3) with $(v,u)=(v_{2},x)$, we have
$a=4+d(u_{1})-(a+b)$. If $d(u_{1})=a+b$, then $a=4$. For the vertex $u_{1}$,
we have $S(u_{1})=4(a+b)+b=a+b-3+6+d(u_{2})$. It follows that
$d(u_{2})=4(a+b)-7>max\\{a+b,d_{G_{0}}(u_{2})\\}$, which is impossible by
Lemma 2.5 (ii). If $d(u_{1})=3\neq a+b$, then $a=7-(a+b)$. Note that $a+b\neq
3,4$. We have $a+b=5$ and $a=2,b=3$ by Lemma 2.5 (iii). By (2.1) and (2.2),
$S(w_{1})=11=4+d(u_{1})+d(u_{n})$. This is impossible since
$d(u_{1})=d(u_{n})$.

Up to now, we have completed the proof of the Lemma. $\square$.

###### Lemma 3.7

Let $G\in{\mathcal{G}}$ with $G_{0}\in{\mathcal{T}}_{6}$. Then $G=H_{i}$ for
$i=11,\dots,15$ (see Fig. 3) or $G\in{\mathcal{G}}_{4}$ (see Fig. 4).

Proof. Let $G_{0}=T_{6}$ (see Fig. 2), where $n,m,p,k\geq 2$. For convenience,
we set $u_{1}=v_{1}=w_{1}=s_{1}$ and $u_{n}=v_{m}=w_{k}=s_{p}$.

Case 1. There is a vertex $v\in\\{u_{2},v_{2},w_{2},s_{2}\\}$ such that
$d_{G_{0}}(v)=2$ and $d(v)=a+b$. Without loss of generality, suppose that
$v=u_{2}$. Applying (2.3) with $(v,u)=(u_{2},x)$, we have

$a=\frac{a+b-2+d(u_{1})+d(u_{3})-(a+b)}{a+b-1}=\frac{d(u_{1})+d(u_{3})-2}{a+b-1}.$
(3.4)

By Lemmas 2.5 (ii), $d(u_{1}),d(u_{3})=4$ or $a+b$. We consider the following
three cases:

Subcase 1. $d(u_{1})=d(u_{3})=a+b$, then $a=2$ by (3.4).

We now show that $d(u_{i})=a+b$ for $1\leq i\leq n$. If $n=3$, then obviously,
$d(u_{i})=a+b$ for $1\leq i\leq n$. If $n\geq 4$, then $d(u_{i})=d(u_{2})=a+b$
for $1<i<n$ and $d(u_{n})=d(u_{1})=a+b$ by Lemma 3.1 (i). Hence $d(u_{i})=a+b$
for $1\leq i\leq n$.

Applying Lemma 2.5 (iv) with $C=u_{1}u_{2}\dots u_{n}v_{m-1}\dots v_{2}u_{1}$,
we have $d(v_{i})\neq a+b$ for some $2\leq i\leq m-1$. It follows from Lemmas
2.5 (ii) and 3.1 (i) that $m\geq 3$ and $d(v_{i})=2$ for all $2\leq i\leq
m-1$. Thus $S(v_{2})=2a+b=a+b+d(v_{3})$. Note that $a=2$. We have
$d(v_{3})=2$. So $m\geq 4$. It follows from Lemma 3.1 (ii) that $m=4$.
Similarly, we have $k=p=4$ and $d(w_{2})=d(w_{3})=d(s_{2})=d(s_{3})=2$.

For the vertex $u_{1}$, $S(u_{1})=2(a+b)+b=a+b-4+6+a+b$ by (2.1) and (2.2).
Hence $b=2$. It follows that $d(u_{i})=a+b=4$ for $1\leq i\leq n$.

Therefore $G\in{\mathcal{G}}_{4}$ (see Fig. 4), where $l_{1}\geq 1$. It is
easy to see that any graph $G\in{\mathcal{G}}_{4}$ is 2-walk $(2,2)$-linear.

Subcase 2. $d(u_{1})=a+b,d(u_{3})=4$ or $d(u_{1})=4,d(u_{3})=a+b$ and $a+b\neq
4$. Then $a=1+\frac{3}{a+b-1}$ is not an integer by (3.4), a contradiction.

Subcase 3. $d(u_{1})=d(u_{3})=4\neq a+b$. Then $n=3$ and $a=\frac{6}{a+b-1}$.
It follows from Lemma 2.5 (iii) that $a+b=3$ and $a=3,b=0$. Thus
$d(u_{2})=a+b=3$. For the vertex $u_{1}$,
$S(u_{1})=12=3+d(v_{2})+d(w_{2})+d(s_{2})$ by (2.1) and (2.2). Note that
$d(v_{2}),d(w_{2}),d(s_{2})\in\\{2,4,a+b\\}$. We have
$d(v_{2})=d(w_{2})=d(s_{2})=a+b=3$. So $S(v_{2})=9=5+d(v_{3})$. Thus
$d(v_{3})=4\neq a+b$. It implies that $m=3$. Similarly, we have $k=p=3$.
Therefore $G=H_{11}$ (see Fig. 3). By (2.3), $H_{11}$ is 2-walk
$(3,0)$-linear.

Case 2. For any vertex $v\in\\{u_{2},v_{2},w_{2},s_{2}\\}$, $d_{G_{0}}(v)=4$
or $d(v)=2$. By Lemma 2.4, $n,m,p,k\leq 4$. Without loss of generality,
suppose that $n\geq m\geq p\geq k$. Then $n\geq m\geq p\geq 3$ and
$d(u_{2})=d(v_{2})=d(s_{2})=2$. By (2.1) and (2.2),
$S(u_{2})=d(u_{1})+d(u_{3})=S(v_{2})=d(u_{1})+d(v_{3})$. Thus
$d(v_{3})=d(u_{3})$. It implies that $m=n$. Similarly, we have $p=n$ and $k=n$
or $2$. Hence $k=p=m=n\in\\{3,4\\}$ or $k=2,p=m=n\in\\{3,4\\}$.

If $G$ has no pendent vertex, then $G=H_{i}$ for $i=12,\dots,15$ (see Fig. 3).
By (2.3), $H_{12}$ is 2-walk $(1,6)$-linear, $H_{13}$ is 2-walk
$(0,8)$-linear, $H_{14}$ is 2-walk $(2,2)$-linear and $H_{15}$ is 2-walk
$(1,4)$-linear.

If $G$ has at least one pendent vertex $x$, then $x\in N(u_{1})$ or $x\in
N(u_{n})$. Without loss of generality, suppose that $x\in N(u_{1})$. Then
$d(u_{1})=a+b\geq 5$. Applying (2.3) with $(v,u)=(u_{1},x)$, we have
$a=\frac{d(w_{2})+2}{a+b-1}$. By Lemma 2.5 (ii), $d(w_{2})=2,4$ or $a+b$. It
implies that $a<2$. This is impossible by Lemma 2.5 (iii).

Up to now, we have competed the proof of the Lemma. $\square$

###### Lemma 3.8

Let $G\in{\mathcal{G}}$ with $G_{0}\in{\mathcal{T}}_{7}$(see Fig. 1). Then
$G=H_{i}$ for $i=16,\dots,23$ (see Fig. 3) or $G\in{\mathcal{G}}_{j}$ for
$j=5,6$ (see Fig. 4).

Proof. Let $G_{0}=T_{7}$ (see Fig. 2), where $n,m,k,l,p,q\geq 2$. For
convenience, we set $u_{1}=w_{1}=s_{1},u_{n}=w_{k}=t_{1},v_{1}=r_{1}=s_{p}$
and $v_{m}=r_{l}=t_{q}$.

If $G$ has no pendent vertex, then $n,m,k,l,p,q\leq 4$ by Lemma 2.4. Without
loss of generality, suppose that $n\geq k,m\geq l,p\geq q$. Then $n=3$ or $4$.
By (2.1) and (2.2),
$S(u_{1})=d(u_{2})+d(w_{2})+d(s_{2})=S(u_{n})=d(u_{n-1})+d(w_{k-1})+d(t_{2})$.
Note that $d(u_{2})=d(u_{n-1}),d(w_{2})=d(w_{k-1})$. We have
$d(s_{2})=d(t_{2})$. It implies that $p=q$. Similarly, we have $k=l$. If
$n=3$, then $m=3,k,p=2$ or $3$ by Lemma 2.4. Hence $G=H_{i}$ for
$i=16,17,18,19$ (see Fig. 3). If $n=4$, then $m=4,k,p=2$ or $4$ by Lemma 2.4.
Hence $G=H_{j}$ for $j=20,21,22,23$ (see Fig. 3). By (2.3), $H_{16}$ is 2-walk
$(2,2)$-linear, $H_{17}$ and $H_{18}$ are 2-walk $(1,4)$-linear, $H_{19}$ is
2-walk $(0,6)$-linear, $H_{20}$ is 2-walk $(3,-1)$-linear, $H_{21}$ and
$H_{22}$ are 2-walk $(2,1)$-linear, $H_{23}$ is 2-walk $(1,3)$-linear.

If $G$ has at least one pendent vertex. Then $a\geq 2,a+b\geq 3$.

We first show that $d(v_{1})=d(v_{m})$.

If $max\\{m,l\\}\geq 4$, then $d(v_{1})=d(v_{m})$ by Lemma 3.1 (i).

If $m,l\leq 3$. By way of contradiction, suppose that $d(v_{1})\neq d(v_{m})$.
By Lemma 2.5 (ii), we may assume that $d(v_{1})=a+b>3,d(v_{m})=3$ without loss
of generality. Applying (2.3) with $(v,u)=(v_{1},v_{3})$, we have

$a=\begin{cases}\frac{d(s_{p-1})-d(t_{q-1})}{a+b-3}&\mbox{if}\ m=3,l=2\
\mbox{or}\ m=2,l=3,\\\ 1+\frac{d(s_{p-1})-d(t_{q-1})}{a+b-3}\quad&\mbox{if}\
m=3,l=3.\end{cases}$

By Lemma 2.5 (ii), $d(s_{p-1}),d(t_{q-1})=2,3$ or $a+b$.

If $m=3,l=2$ or $m=2,l=3$, then $d(s_{p-1})=a+b,d(t_{q-1})=2$ since $a\geq
2,a+b\geq 3$. So $a=1+\frac{1}{a+b-3}$. It implies that $a+b=4$ and $a=b=2$.
By (2.1) and (2.2), $S(v_{3})=6+d(v_{2})=8$. So $d(v_{2})=2$ and $S(v_{2})=6$
by (2.2). On the other hand, $S(v_{2})=7$ by (2.1), a contradiction.

If $m=l=3$, then $d(s_{p-1})=a+b\neq 3,d(t_{q-1})=3$ or
$d(s_{p-1})=a+b,d(t_{q-1})=2$ since $a\geq 2,a+b\geq 3$. If
$d(s_{p-1})=a+b\neq 3,d(t_{q-1})=3$, then $a+b\geq 4$ and $a=2$. Thus $b\geq
2$. By (2.1) and (2.2), $S(v_{3})=6+b=d(v_{2})+d(r_{2})+3$, which is
impossible since $d(v_{2}),d(r_{2})=2$ or $2+b$ and $b\geq 2$. If
$d(s_{p-1})=a+b,d(t_{q-1})=2$, then $a=2+\frac{1}{a+b-3}$. It implies that
$a+b=4$ and $a=3,b=1$. By (2.1) and (2.2), $S(v_{3})=d(v_{2})+d(r_{2})+2=10$.
Note that $d(v_{2}),d(r_{2})=2$ or $4$ by Lemma 2.5 (ii), we have
$d(v_{2})=d(r_{2})=4$. Thus $S(v_{2})=13$ by (2.2). On the other hand,
$S(v_{2})=9$ by (2.1), a contradiction.

Hence $d(v_{1})=d(v_{m})$.

Next, we show that $d(v_{1})=d(v_{m})=a+b$. On the contrary, suppose that
$d(v_{1})=d(v_{m})=3\neq a+b$ by Lemma 2.5 (ii). Then $a+b\geq 4$. Note that
$max\\{m,l\\}\geq 3$. Without loss of generality, suppose that $m\geq 3$. By
Lemma 2.5 (ii), we have $d(v_{2})=a+b$ or $2$.

If $d(v_{2})=a+b$. Applying (2.3) with $(v,u)=(v_{2},x)$, we have
$a=\frac{d(v_{3})+1}{a+b-1}$. By Lemma 2.5 (ii), $d(v_{3})=2,3$ or $a+b$. This
together with $a+b\geq 4$ implies that $a<2$. It contradicts the fact that
$a\geq 2$.

If $d(v_{2})=2$. Applying (2.3) with $(v,u)=(v_{2},x)$, we have
$a=3+d(v_{3})-(a+b)$. If $m\geq 4$, then $d(v_{3})=2$ by Lemma 3.1 (i). Note
that $a+b\geq 4$. We have $a=5-(a+b)\leq 1$. It contradicts the fact $a\geq
2$. Thus $m=3$. Hence $d(v_{3})=3$ and $a=6-(a+b)$. Note that $a+b\geq 4,a\geq
2$. We have $a+b=4$ and $a=b=2$. By (2.1) and (2.2),
$S(v_{1})=2+d(r_{2})+d(s_{p-1})=8$. So $d(r_{2})+d(s_{p-1})=6$.

If $l=2$, then $d(r_{2})=d(v_{m})=3$. So $d(s_{p-1})=3\neq a+b$. It implies
that $p=2$ and $d(u_{1})=d(s_{p-1})=3$. Similarly, we get $q=2$ and
$d(u_{n})=3$. By (2.1) and (2.2), $S(u_{1})=3+d(w_{2})+d(u_{2})=8$. Note that
$d(w_{2}),d(u_{2})=2,3$ or $4$ by Lemma 2.5 (ii). It follows that
$d(u_{2})=2,d(w_{2})=3$ or $d(u_{2})=3,d(w_{2})=2$. We may suppose that
$d(u_{2})=2,d(w_{2})=3$ without loss of generality. Then $k=3$ and
$d(u_{i})=2$ for $2\leq i\leq n-1$ by Lemma 3.1 (i). Hence $G$ has no pendent
vertex. This is a contradiction.

If $l\geq 3$, then $d(r_{2})=2$ or $4$. If $d(r_{2})=2$, then
$d(s_{p-1})=6-d(r_{2})=4$. Thus $S(s_{p-1})=10$ by (2.2). This is impossible
since $S(s_{p-1})=4-2+3+d(s_{p-2})\leq 9$ by (2.1). If $d(r_{2})=4$, then
$S(r_{2})=10$ by (2.2). This is also impossible since
$S(r_{2})=4-2+3+d(r_{3})\leq 9$ by (2.1).

Hence $d(v_{1})=d(v_{m})=a+b$. Dually, we have $d(u_{1})=d(u_{n})=a+b$.

Applying Lemma 2.5 (iv) with $C=v_{1}v_{2}\dots v_{m}r_{l-1}\dots r_{2}v_{1}$,
we have, without loss of generality, $m\geq 3$ and $d(v_{i})\neq a+b$ for some
$2\leq i\leq m-1$. So $d(v_{i})=2$ for all $2\leq i\leq m-1$ by Lemmas 2.5
(ii) and 3.1.

Applying (2.3) with $(v,u)=(v_{1},x)$ and $(v,u)=(v_{2},x)$, respectively. We
have

$a=\frac{d(r_{2})+d(s_{p-1})-1}{a+b-1}\ \mbox{and}\ a=d(v_{3}),$ (3.5)

respectively.

We claim that $m\geq 4$. Otherwise, suppose that $m=3$. Then $a=d(v_{3})=a+b$
and $d(r_{2})+d(s_{p-1})=a(a+b-1)+1\geq 3(a+b)-2>2(a+b)$, which is impossible
since $d(r_{2}),d(s_{p-1})=2$ or $a+b$ by Lemma 2.5 (ii). Hence $m\geq 4$.
Therefore $m=4$ by Lemma 3.1 (ii). Thus $a=d(v_{3})=2$. It follows from (3.5)
that $d(r_{2})+d(s_{p-1})=2(a+b)-1$. By Lemma 2.5 (iii),
$d(r_{2}),d(s_{p-1})=2$ or $a+b$.

If $d(r_{2})=d(s_{p-1})=2$, then $a+b=2.5$, a contradiction.

If $d(r_{2})=d(s_{p-1})=a+b$, then $2(a+b)=2(a+b)-1$, a contradiction.

If $d(r_{2})=2,d(s_{p-1})=a+b$, then $a+b=3$. So $a=2,b=1$.

By Lemma 3.1 (i), $d(s_{i})=d(s_{p-1})=3$ for $2\leq i\leq p-1$.

For the vertex $u_{1}$, $S(u_{1})=3+d(u_{2})+d(w_{2})=7$ by (2.1) and (2.2).
By Lemma 2.5 (ii), $d(u_{2}),d(w_{2})=2$ or $3$. It follows that
$d(u_{2})=d(w_{2})=2$. So $S(u_{2})=3+d(u_{3})=5$. Thus $d(u_{3})=2$ and
$n\geq 4$. Hence $n=4$ by Lemma 3.1 (ii).

Similarly, we have $d(w_{3})=d(r_{2})=2$ and $k=l=4$.

By (2.1) and (2.2), $S(u_{4})=4+d(t_{2})=7$. So $d(t_{2})=3$. Hence
$d(t_{i})=3$ for $1\leq i\leq q-1$ by Lemma 3.1 (i).

Therefore $G\in{\mathcal{G}}_{5}$ (see Fig. 4), where
$max\\{k_{1},k_{2}\\}\geq 1$. It is easy to see that any graph
$G\in{\mathcal{G}}_{5}$ is $2$-walk $(2,1)$-linear.

If $d(r_{2})=a+b,d(s_{p-1})=2$, then with a similar argument of the case
$d(r_{2})=2,d(s_{p-1})=a+b$, we have $G\in{\mathcal{G}}_{6}$ is $2$-walk
$(2,1)$-linear (see Fig. 4), where $max\\{k_{1},k_{2}\\}\geq 1$.

Up to now, we have complete the proof of the Lemma. $\square$

###### Lemma 3.9

Let $G\in{\mathcal{G}}$ with $G_{0}\in{\mathcal{T}}_{8}$. Then $G\cong H_{i}$
for $i=24,\dots,30$ (see Fig. 3) or $G\in{\mathcal{G}}_{j}$ for $j=7,8$ (see
Fig. 4).

Proof. Let $G_{0}=T_{8}$ (see Fig. 2), where $n,m,k,l,p,q\geq 2$. For
convenience, we set $u_{1}=v_{1}=w_{1}$, $u_{n}=t_{1}=s_{p}$,
$v_{m}=r_{1}=t_{q}$ and $w_{k}=s_{1}=r_{l}$.

Case 1. There is a vertex $v\in\\{w_{2},v_{2},u_{2}\\}$ with $d_{G_{0}}(v)=2$
and $d(v)=a+b$. Without loss of generality, suppose that $v=w_{2}$. Then
$k\geq 3$ and $d(w_{i})=a+b$ for $2\leq i\leq k-1$ by Lemma 3.1 (i). In
particular, $,a\geq 2,a+b\geq 3$ by Lemma 2.5 (iii).

Applying Lemma 2.3 with $(v,u)=(w_{2},x)$, we have
$a=\frac{d(w_{1})+d(w_{3})-2}{a+b-1}$. By Lemma 2.5 (ii), we have
$d(w_{1}),d(w_{3})=3$ or $a+b$.

If $d(w_{1})=d(w_{3})=3\neq a+b$, then $a+b\geq 4$ and $a=\frac{4}{a+b-1}<2$,
a contradiction.

If $d(w_{1})=a+b,d(w_{3})=3$ or $d(w_{3})=a+b,d(w_{1})=3$ and $a+b\neq 3$,
then $a=\frac{a+b+1}{a+b-1}=1+\frac{2}{a+b-1}<2$, a contradiction.

If $d(w_{1})=d(w_{3})=a+b$, then $a=2$. We claim that $a+b=3$. Otherwise, let
$a+b>3$. For the vertex $w_{1}$,
$S(w_{1})=2(a+b)+b=a+b-3+a+b+d(u_{2})+d(v_{2})$. Thus
$d(u_{2})+d(v_{2})=a+b+1$. By Lemma 2.5 (ii), $d(u_{2}),d(v_{2})=2,3$ or
$a+b$. Note that $a+b>3$. We have $d(u_{2})=2,d(v_{2})=3$ or
$d(u_{2})=3,d(v_{2})=2$ or $d(u_{2})=d(v_{2})=3$. Without loss of generality,
we consider the following two cases:

If $d(u_{2})=2,d(v_{2})=3$, then $a+b=4$ and $m=2$. Note that $a=2$. We have
$b=2$. If $k\geq 4$, then $d(w_{k})=d(w_{1})=4$ by Lemma 3.1 (i). If $k=3$,
then $d(w_{k})=d(w_{3})=4$. So $d(r_{3})=2$ or $4$ by Lemma 2.5 (ii). On the
other hand, $S(v_{2})=4+d(r_{2})+d(t_{q-1})=8$ by (2.1) and (2.2). So
$d(r_{2})=d(t_{q-1})=2$. By (2.1) and (2.2), $S(r_{2})=6=3+d(r_{3})$. Thus
$d(r_{3})=3$, a contradiction.

If $d(u_{2})=d(v_{2})=3$, then $a+b=5$ and $m=n=2$. Note that $a=2$. We have
$b=3$. By (2.1) and (2.2), $S(v_{2})=5+d(r_{2})+d(t_{q-1})=9$. Thus
$d(r_{2})=d(t_{q-1})=2$. Hence $S(r_{2})=7=3+d(r_{3})$. This is impossible
since $d(r_{3})\in\\{2,3,5\\}$.

Therefore $a+b=3$ and $a=2,b=1$.

By (2.1) and (2.2), $S(w_{1})=7=3+d(v_{2})+d(u_{2})$. So
$d(v_{2})=d(u_{2})=2$. Hence $S(v_{2})=5=3+d(v_{3})$. It follows that
$d(v_{3})=2$ and $m\geq 4$. Therefore $m=4$ by Lemma 3.1 (ii).

Similarly, we have
$n=l=p=4,d(u_{2})=d(u_{3})=d(r_{2})=d(r_{3})=d(s_{2})=d(s_{3})=2$ and
$d(t_{i})=3$ for $2\leq i\leq q-1$.

Therefore $G\in{\mathcal{G}}_{8}$ (see Fig. 4), where
$max\\{k_{1},k_{2}\\}\geq 1$. It is easy to see that any graph
$G\in{\mathcal{G}}_{8}$ is 2-walk $(2,1)$-linear.

Case 2. For any vertex $v\in\\{w_{2},v_{2},u_{2}\\}$, we have $d_{G_{0}}(v)=3$
or $d(v)=2$.

If $G$ has no pendent vertex, then $n,m,k,l,p,q\leq 4$ by Lemma 2.4. If
$n=m=k=l=p=q=2$, then $G$ is regular. It is well known that a graph is regular
if and only if it has exactly one main eigenvalues. Thus
$max\\{n,m,k,p,q\\}\geq 3$. Without loss of generality, suppose that $n\geq
3$. We consider the following two cases:

Subcase 1. $n=3$. Then $S(u_{2})=6$ and $m,k,l,p,q=2$ or $3$ by Lemma 2.4.

If $m=k=2$, then $S(u_{1})=8=S(u_{3})=2+d(t_{2})+d(s_{p-1})$. So
$d(t_{2})=d(s_{p-1})=3$ and hence $p=q=2$. Similarly,
$S(u_{1})=8=S(v_{2})=6+d(r_{2})$. Thus $d(r_{2})=2$ and $l=3$. Therefore
$G=H_{24}$ (see Fig. 3). By (2.3), $H_{24}$ is 2-walk $(2,2)$-linear. With a
similar argument, we have:

If $m=2,k=3$ or $m=3,k=2$, then $G=H_{25}$ is 2-walk $(1,4)$-linear (see Fig.
3).

If $m=k=3$, then $G=H_{26}$ is 2-walk $(0,6)$-linear (see Fig. 3).

Subcase 2. $n=4$. Then $m,k,l,p,q=2$ or $4$ by Lemma 2.4. With a similar
argument of Subcase 1, we have the following cases:

If $m=k=2$, then $G=H_{27}$ is 2-walk $(3,-1)$-linear (see Fig. 3).

If $m=2,k=4$ or $m=4,k=2$, then $G=H_{28}$ is 2-walk $(2,1)$-linear (see Fig.
3).

If $m=k=4$, then $G=H_{29}$ is 2-walk $(1,3)$-linear (see Fig. 3).

If $G$ has at least one pendent vertex $x$, then $x\in N(v)$ for
$v\in\\{w_{1},v_{m},u_{n},w_{k},r_{i_{1}},t_{i_{2}},s_{i_{3}}\\}$, where
$2\leq i_{1}\leq l-1,2\leq i_{2}\leq q-1,2\leq i_{3}\leq p-1$. If
$v\in\\{r_{i_{1}},t_{i_{2}},s_{i_{3}}\\}$, then with a similar argument of
Case 1, we have $G\in\mathcal{G}_{8}$. Hence we may suppose that
$v\in\\{w_{1},v_{m},u_{n}\\}$. In particular, assume that $x\in N(w_{1})$
without loss of generality. Then $d(w_{1})=a+b\geq 4$ and $d(u)=d_{G_{0}}(u)$
for $u\in\\{r_{i_{1}},t_{i_{2}},s_{i_{3}}\\}$, where $2\leq i_{1}\leq
l-1,2\leq i_{2}\leq q-1,2\leq i_{3}\leq p-1$. Applying Lemma (2.3) with
$(v,u)=(w_{1},x)$, we have

$a=\frac{a+b-3+d(u_{2})+d(v_{2})+d(w_{2})-(a+b)}{a+b-1}=\frac{d(u_{2})+d(v_{2})+d(w_{2})-3}{a+b-1}.$

Note that $d(u_{2}),d(v_{2}),d(w_{2})=2,3$ or $a+b$ and $a+b\geq 4$. We
consider the following cases without loss of generality:

If $d(u_{2})=d(v_{2})=d(w_{2})=2$, then $a=\frac{3}{a+b-1}<2$, a
contradiction.

If $d(u_{2})=d(v_{2})=2,d(w_{2})=3$, then $a=\frac{4}{a+b-1}<2$, a
contradiction.

If $d(u_{2})=d(v_{2})=2,d(w_{2})=a+b$, then $a=1+\frac{2}{a+b-1}<2$, a
contradiction.

If $d(u_{2})=2,d(v_{2})=d(w_{2})=3$, then $a=\frac{5}{a+b-1}<2$, a
contradiction.

If $d(u_{2})=2,d(v_{2})=3,d(w_{2})=a+b$, then $m=2$ and $a=1+\frac{3}{a+b-1}$.
By Lemmas 2.2 and 2.5 (ii), we have $a+b=4$ and $a=2$. Hence
$d(w_{i})=d(w_{2})=4$ for $2\leq i\leq k-1$. By (2.1) and (2.2),
$S(w_{k-1})=4+2+d(w_{k})=10$. Thus $d(w_{k})=4$. Similarly,
$S(v_{2})=4+d(r_{2})+d(t_{q-1})=8$. It implies that $d(r_{2})=d(t_{q-1})=2$.
Thus $S(r_{2})=6=3+d(r_{3})$. Hence $d(r_{3})=3$. On the other hand,
$d(r_{3})\in\\{2,4\\}$ by Lemma 2.5 (ii) and the fact that $d(w_{k})=4$. This
is a contradiction.

If $d(u_{2})=2,d(v_{2})=d(w_{2})=a+b$, then $a=2+\frac{1}{a+b-1}$ is not an
integer, a contradiction.

If $d(u_{2})=d(v_{2})=d(w_{2})=3$, then $n=m=k=2$ and $a=\frac{6}{a+b-1}$. It
follows from Lemma 2.5 (iii) that $a+b=4$ and $a=b=2$. By (2.1) and (2.2),
$S(v_{2})=4+d(r_{2})+d(t_{q-1})=8$. It implies that $d(r_{2})=d(t_{q-1})=2$.
Hence $S(r_{2})=3+d(r_{3})=6$. It follows that $d(r_{3})=3$ and $l=3$.
Similarly, we have $p=q=3$. Therefore $G=H_{30}$ (see Fig. 3). By (2.3),
$H_{30}$ is 2-walk $(2,2)$-linear.

If $d(u_{2})=d(v_{2})=3,d(w_{2})=a+b$, then $n=m=2$ and $a=1+\frac{4}{a+b-1}$.
Thus $a+b=5$ and $a=2$ by Lemma 2.5 (iii). Hence $d(w_{1})=d(w_{2})=a+b=5$.
For the vertex $v_{2}$, $S(v_{2})=5+d(r_{2})+d(t_{q-1})=9$. It implies that
$d(r_{2})=d(t_{q-1})=2$. Thus $S(r_{2})=3+d(r_{3})=7$, which is impossible
since $d(r_{3})\in\\{2,3,5\\}$ by Lemma 2.5 (ii).

If $d(u_{2})=3,d(v_{2})=d(w_{2})=a+b$, then $a=2+\frac{2}{a+b-1}$ is not an
integer, a contradiction.

If $d(u_{2})=d(v_{2})=d(w_{2})=a+b$, then $n=m=k=2$ and $a=3$. We claim that
$p=l=2$. Otherwise, let $p,l>2$. By (2.1),
$S(w_{1})=a+b-3+3(a+b),S(w_{2})=a+b-3+a+b+d(s_{2})+d(r_{l-1})$. Note that
$d(s_{2}),d(r_{l-1})=2$ by assumption. We have $S(w_{1})>S(w_{2})$. On the
other hand, $S(w_{1})=S(w_{2})$ by (2.2), a contradiction. Hence $p=l=2$.
Similarly, we have $q=2$. Thus $G\in{\mathcal{G}}_{7}$ (see Fig. 4), where
$b\geq 1$. It is easy to see that any graph $G\in{\mathcal{G}}_{7}$ is 2-walk
$(3,b)$-linear.

Up to now, we have complete the proof of the Lemma. $\square$

###### Theorem 3.10

The graphs $H_{i}$ for $i=1,\dots,30$ and those in ${\mathcal{G}}_{j}$ for
$j=1,\dots,8$ are all connected tricyclic graphs with exactly two main
eigenvalues.

Proof. It follows directly from Lemmas 3.2–3.9. $\square$

## References

  * [1] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan, New York, 1976.
  * [2] D. Cvetkovic, P. Rowlinson, S. Simic, Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.
  * [3] E.M. Hagos, Some results on graph spectra. Linear Algebra Appl. 356 (2002) 103–111.
  * [4] Y.P. Hou, H.Q. Zhou, Trees with exactly two main eigenvalues, Acta of Hunan Normal University. 28(2) (2005) 1–3 (in Chinese).
  * [5] Y.P. Hou, F. Tian, Unicyclic graphs with exactly two main eigenvalues, Appl. Math. Lett. 19 (2006) 1143–1147.
  * [6] Z.Q. Hu, S.C. Li, C.F. Zhu, Bicyclic graphs with exactly two main eigenvalues, Linear Algebra Appl. 431 (2009) 1848–1857.
  * [7] L.S. Shi, On graphs with given main eigenvalues, Appl. Math. Lett. 22 (2009) 1870–1874.
  * [8] X.Y. Geng, S.C. Li, The spectral radius of tricyclic graphs with $n$ vertices and $k$ pendant vertices, Linear Algebra Appl. 428 (2008) 2639–2653.