Cent. Eur. J. Math. • 11(10) • 2013 • 1800-1816 DOI: 10.2478/s11533-013-0283-z

Central European Journal of Mathematics

Tricyclic graphs with exactly two main eigenvalues Research Article Xiaoxia Fan1∗ , Yanfeng Luo1† , Xing Gao1‡

1 Department of Mathematics, Lanzhou University, Tianshui Road South 222, Lanzhou, Gansu 730000, China

Received 25 May 2012; accepted 2 November 2012 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. Let G0 be the graph obtained from G by deleting all pendant vertices and δ(G) the minimum degree of vertices of G. In this paper, all connected tricyclic graphs G with δ(G0 ) ≥ 2 and exactly two main eigenvalues are determined. MSC:

05C50

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

© Versita Sp. z o.o.

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 Cvetković [2] is that of how to characterize graphs with exactly k, k ≥ 2, main eigenvalues. Hagos [4] gave an alternative characterization of graphs with exactly two main eigenvalues. Recently, Hou and Zhou [6] 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 Cn and Pn 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 Crk for some positive integers k, r ∗ † ‡

1800

E-mail: [email protected] E-mail: [email protected] E-mail: [email protected]

X. Fan, Y. Luo, X. Gao

with r ≥ 3, where Crk is the graph obtained from Cr by attaching k > 0 pendant vertices to every vertex of Cr , are the only connected unicyclic graphs with exactly two main eigenvalues. Hu et al. [7] and Shi [8] characterized independently all connected bicyclic graphs with exactly two main eigenvalues. This paper will continue the line of this research and determine a class of connected tricyclic graphs with exactly two main eigenvalues. For any tricyclic graph G, the base of G, denoted by GB , is the minimal tricyclic subgraph of G. Clearly, GB is the unique tricyclic subgraph of G containing no pendant vertex, and G can be obtained from GB by attaching trees to some vertices of GB . It follows from [3] that there are eight types of bases for tricyclic graphs, say, Ti , i = 1, . . . , 8, which are depicted in Figure 1.

Figure 1.

2.

The eight types of bases for tricyclic graphs.

Preliminaries

In this section, we will present some notation 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) = dG (v) and N(v) = NG (v) the degree of vertex v and the set of all neighbors of v in G. Let X S(v) = d(u). (1) u∈N(v)

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)

holds for every vertex v ∈ V (G). An internal path of G is a walk v0 v1 . . . vs such that the vertices v0 , v1 , . . . , vs are distinct, d(v0 ) > 2, d(vs ) > 2, and d(vi ) = 2 for 0 < i < s. An internal cycle of G is a closed walk v0 v1 . . . vs such that v0 = vs , d(v0 ) = d(vs ) > 2, and d(vi ) = 2 for 0 < i < s. If R is an internal path or an internal cycle of G, the length of R, denoted by l(R), is defined as the number of vertices of R minus 1.

Lemma 2.1 ([4]). 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 ([7]). Let G be a 2-walk (a, b)-linear graph and v, u be two vertices of G with unequal degrees d(v), d(u), respectively. Then a=

S(v) − S(u) , d(v) − d(u)

b=

d(u)S(v) − d(v)S(u) . d(v) − d(u)

(3)

1801

Tricyclic graphs with exactly two main eigenvalues

In the following, for convenience, we always assume that G is the set of connected tricyclic graphs with exactly two main eigenvalues, x is a pendant vertex of G (if existing). For each G ∈ G, let G0 be the graph obtained from G by deleting all pendant vertices. Let δ(G) be the minimum degree of vertices of G. [7, Lemma 3.1] holds for any graph G. This is because the authors did not use any information on the graph to be bicyclic. Hence we have the following two lemmas.

Lemma 2.4. Let G ∈ G and R = x1 x2 . . . xt be an internal path or internal cycle of length at least 2 in G. Then l(R) ≤ 3. In particular, if l(R) = 3, then there exists no path Q = y1 y2 y3 in G such that d(y1 ) = d(y3 ) = d(x1 ) and d(y2 ) = 2.

[7, Lemmas 3.3, 3.4 (ii), 3.5–3.7] give a characterization of bicyclic graphs with two main eigenvalues. In fact, their results and their proof hold for an arbitrary graph with at least one cycle and one pendant vertex and δ(G0 ) ≥ 2. We have the following lemma.

Lemma 2.5. Let G ∈ G and v ∈ V (G0 ). If δ(G) = 1 and δ(G0 ) ≥ 2, then (i) G0 ∈ Ti , i = 1, . . . , 8, see Figure 1; (ii) d(v) = dG0 (v) or a + b; (iii) if G has at least one pendant vertex x, then S(x) = a + b ≥ 3 and a ≥ 2; (iv) for an internal cycle C = x1 x2 . . . xt x1 of G0 with dG0 (x1 ) ≥ 3, dG0 (x2 ) = 2, if G has at least one pendant vertex, then there is an integer i ∈ {1, 2, . . . , t} such that d(xi ) = 6 a + b.

3.

Tricyclic graphs with exactly two main eigenvalues

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

Lemma 3.1. Let G ∈ G have at least one pendant vertex and δ(G0 ) ≥ 2, R = x1 x2 . . . xt be an internal path or an internal cycle of length at least 3 in G0 with dG0 (x1 ) = dG0 (xt ) ∈ {3, 4} or dG0 (x1 ) = 3, dG0 (xt ) = 5. And let all vertices in N(x1 ) and N(xt ) lie in some internal paths or internal cycles of G when dG0 (x1 ) = dG0 (xt ) = 4. Then: (i) d(x2 ) = d(x3 ) = . . . = d(xt−1 ) ∈ {2, a + b} and d(x1 ) = d(xt ); (ii) if d(x2 ) = 2, then l(R) = 3; (iii) if R is an internal cycle of G0 with dG0 (x1 ) ∈ {3, 4}, then l(R) = 3 and d(x2 ) = d(x3 ) = 2; in particular, if dG0 (x1 ) = 3, then a = 2; (iv) if R is an internal cycle of G0 with dG0 (x1 ) = 5, then l(R) = 3, d(x2 ) = d(x3 ) ∈ {2, 3}; in particular, if d(x2 ) = d(x3 ) = 3, then d(x1 ) = 5 and a = 3, b = 0.

Proof. (i) By way of contradiction, assume that there is an integer i ∈ {2, 3, . . . , t − 2} such that d(xi ) = 6 d(xi+1 ). By Lemma 2.5 (ii), we may assume that d(xi ) = 2 and d(xi+1 ) = a + b. Applying (3) with (v, u) = (xi+1 , x), we have a=

S(xi+1 ) − S(x) a + b − 2 + 2 + d(xi+2 ) − (a + b) d(xi+2 ) = = . d(xi+1 ) − d(x) a+b−1 a+b−1

This together with Lemma 2.5 (iii) implies that d(xi+2 ) = a(a + b − 1) ≥ 2(a + b − 1) ≥ a + b + 1 > max {a + b, 3}.

1802

(4)

X. Fan, Y. Luo, X. Gao

Hence d(xi+2 ) = dG0 (xi+2 ) > 3 by Lemma 2.5 (ii). Note that we have d(xj ) ∈ {a + b, 2} for 2 ≤ j ≤ t − 1. Thus xi+2 = x1 or xi+2 = xt . If dG0 (x1 ) = dG0 (xt ) = 3, then d(xi+2 ) ∈ {d(x1 ), d(xt )} ⊆ {3, a + b}, contrary to (4). If dG0 (x1 ) = dG0 (xt ) = 4, then d(x1 ), d(xt ) ∈ {4, a + b}. It follows from (4) that d(xi+2 ) = a(a + b − 1) = 4. This together with Lemma 2.5 (iii) implies that a = 2, b = 1. If d(x2 ) = 2, then S(x2 ) = 5 by (2). On the other hand, dG0 (x1 ) = 4 > a+b, so d(x1 ) = 4 by Lemma 2.5 (ii). Thus by (1), S(x2 ) = d(x1 ) + d(x3 ) = 4 + d(x3 ) > 5, a contradiction. If d(x2 ) = a + b = 3, then S(x1 ) = ad(x1 ) + b = 9 = 3 + d(w1 ) + d(w2 ) + d(w3 ), where w1 , w2 , w3 ∈ N(x1 ). Note that all vertices in N(x1 ) lie in cycles. So d(wi ) = 2, i = 1, 2, 3. Thus S(w1 ) = 2d(w1 ) + 1 = 5 = d(x1 ) + d(u), where u ∈ N(w1 ). This implies that d(u) = 1, which is impossible since w1 lies in an internal path or internal cycle. If dG0 (x1 ) = 3, dG0 (xt ) = 5, then by (4), d(xi+2 ) = d(xt ) = dG0 (xt ) = 5 and a(a + b − 1) = 5. This is impossible since a ≥ 2, a + b ≥ 3. Hence d(x2 ) = d(x3 ) = . . . = d(xt−1 ) ∈ {2, a + b}. Therefore S(x2 ) = S(xt−1 ) by (2). On the other hand, by (1), S(x2 ) = d(x2 ) − 2 + d(x1 ) + d(x3 ), S(xt−1 ) = d(xt−1 ) − 2 + d(xt ) + d(xt−3 ). It follows that d(x1 ) = d(xt ). (ii) Suppose that l(R) ≥ 4. Then d(x3 ) = d(x4 ) = 2 by (i). Applying (3) with (v, u) = (x3 , x), we have a = 4 − (a + b), which is impossible by Lemma 2.5 (iii). (iii) By Lemma 2.5 (ii), we have d(x2 ) ∈ {2, a + b}. If d(x2 ) = a + b, then d(xi ) = a + b for 2 ≤ i ≤ t − 1 by (i). Thus d(x1 ) = dG0 (x1 ) = 6 a + b by Lemma 2.5 (iv). Applying (3) with (v, u) = (x2 , x), we have a=

dG (x1 ) − 1 a + b − 2 + d(x1 ) + a + b − (a + b) d(x1 ) − 1 = 1+ = 1+ 0 . a+b−1 a+b−1 a+b−1

(5)

Note that dG0 (x1 ) = 3, 4 and dG0 (x1 ) = 6 a + b ≥ 3. It follows from (5) that a can not be an integer. This contradicts Lemma 2.2. Hence d(x2 ) = 2. Therefore l(R) = 3 and d(x3 ) = d(x2 ) = 2. In particular, if dG0 (x1 ) = 3, then a = 2 + d(x1 ) − (a + b) by applying (3) with (v, u) = (x2 , x). If d(x1 ) = a + b, then a = 2. If d(x1 ) = dG0 (x1 ) = 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(x2 ) ∈ {2, a + b}. If d(x2 ) = 2, then l(R) = 3 and d(x3 ) = 2 by (i) and (ii). If d(x2 ) = a + b, then d(xi ) = a + b for 2 ≤ i ≤ t − 1 by (i). So d(x1 ) = dG0 (x1 ) = 5 6= a + b by Lemma 2.5 (iv). Applying (3) with (v, u) = (x2 , x), we have a = 1 + 4/(a + b − 1). Thus a + b = 3 and a = 3 by Lemmas 2.2 and 2.5 (iii). Suppose that l(R) ≥ 4. Then d(x2 ) = d(x3 ) = d(x4 ) = a + b = 3 by (ii). Applying (3) with (v, u) = (x3 , x), we have a = 2. It is a contradiction. Therefore l(R) = 3.

Lemma 3.2. Let G ∈ G have at least one pendant vertex and δ(G0 ) ≥ 2, R = x1 x2 . . . xt x1 be an internal cycle of length at least 3 in G0 with dG0 (x1 ) = 6. Then exactly one of the following holds: (i) l(R) = 3 and d(x2 ) = d(x3 ) = 2; (ii) l(R) = 5, d(x1 ) = 6, d(x2 ) = d(x5 ) = 4 and d(x3 ) = d(x4 ) = 2; (iii) l(R) = 4, d(x1 ) = 6, d(x2 ) = d(x4 ) = 3 and d(x3 ) = 2.

Proof. Let xt+1 = x1 . Clearly, either d(x2 ) = d(x3 ) = . . . = d(xt ), or there exist i ∈ {2, 3, . . . , t} such that d(xi ) = 6 d(xi+1 ). First assume that d(x2 ) = d(x3 ) = . . . = d(xt ). Then by Lemma 2.5 (ii), we have d(x2 ) = d(x3 ) = . . . = d(xt ) ∈ {2, a + b}. Furthermore, note that we have dG0 (x1 ) = 6, dG0 (x2 ) = 2 and G has at least one pendant vertex. By Lemma 2.5 (iv), there exists k ∈ {1, . . . , t} such that d(xk ) 6= a + b. We claim that k ∈ {2, 3, . . . , t}. Otherwise, let k = 1, then d(x1 ) = dG0 (x1 ) = 6, d(x2 ) = d(x3 ) = . . . = d(xt ) = a + b. Applying (2) with (v, u) = (x2 , x), we have a=

a + b − 2 + d(x1 ) + a + b − (a + b) 5 =1+ . a+b−1 a+b−1

By Lemma 2.5 (iii), a + b ≥ 3, so a is not an integer, which is impossible by Lemma 2.2. Hence k ∈ {2, . . . , t}. Therefore d(x2 ) = d(x3 ) = . . . = d(xt ) = 2. This together with Lemma 2.4 implies that t = 3 and l(R) = 3. (i) follows.

1803

Tricyclic graphs with exactly two main eigenvalues

Now assume that there exists i ∈ {2, 3, . . . , t − 1} such that d(xi ) 6= d(xi+1 ). By Lemma 2.5 (ii), we may assume that d(xi ) = 2 and d(xi+1 ) = a+b. Applying (2) with (v, u) = (xi+1 , x), with the same argument as in the proof of Lemma 3.1 (i), we have d(xi+2 ) = a(a + b − 1) = dG0 (xi+2 ) > 3. Thus xi+2 = x1 , d(x1 ) = dG0 (x1 ) = 6 and a(a + b − 1) = 6. By Lemma 2.5 (iii), we have a = b = 2 or a = 3, b = 0, we consider the following two cases: Case 1: a = b = 2. By Lemma 2.5 (ii), we have d(x2 ) = 2 or a + b. If d(x2 ) = 2, then S(x2 ) = ad(x2 ) + b = 6 = d(x1 ) + d(x3 ). Note that d(x1 ) = 6, we have d(x3 ) = 0, which is impossible. If d(x2 ) = a + b = 4, then S(x2 ) = 2d(x2 ) + b = 10 = d(x1 ) + d(x3 ) + 2 = 8 + d(x3 ). So d(x3 ) = 2. Thus S(x3 ) = 6 = d(x2 ) + d(x4 ). It follows that d(x4 ) = 2. Hence S(x4 ) = 6 = d(x3 ) + d(x5 ), which implies that d(x5 ) = 4. Therefore S(x5 ) = 10 = d(x4 ) + d(x6 ) + 2 which implies that d(x6 ) = 6 ∈ / {2, a + b}. Thus x6 = x1 and t = 5, (ii) follows. Case 2: a = 3, b = 0. Similarly, we have d(x2 ) = 2 or a + b. If d(x2 ) = 2, S(x2 ) = ad(x2 ) + b = 6 = d(x1 ) + d(x3 ) = 6 + d(x3 ). This implies that d(x3 ) = 0, which is impossible. If d(x2 ) = a + b = 3, then S(x2 ) = ad(x2 ) + b = 9 = d(x1 ) + d(x3 ) + 1. It follows that d(x3 ) = 2. So S(x3 ) = ad(x3 ) + b = 6 = d(x2 ) + d(x4 ). Thus d(x4 ) = 3. Hence S(x4 ) = ad(x4 ) + b = 9 = d(x3 ) + d(x5 ) + 1. This implies that d(x5 ) = 6 ∈ / {2, a + b}. Therefore x5 = x1 and t = 4. (iii) follows.

Lemma 3.3. Let G ∈ G with δ(G0 ) ≥ 2 and G0 ∈ T1 , see Figure 1. Then G = Hi for i = 1, 2, 3, see Figure 3.

Figure 2.

1804

Graphs Ti for i = 1, . . . , 8.

X. Fan, Y. Luo, X. Gao

Figure 3.

Graphs Hi for i = 1, . . . , 32.

If G0 ∈ T1 , then dG0 (u1 ), dG0 (v1 ), dG0 (w1 ) ∈ {3, 4, 5, 6}. If dG0 (u1 ), dG0 (v1 ), dG0 (w1 ) ∈ {3, 4, 5}, then each internal cycle of G0 has the length equal to 3 by Lemmas 2.4 and 3.1. Hence G0 = T1 , see Figure 2, where n, m, k ≥ 1 and max {n, m, k} ≥ 2. For convenience, we set wk = vm = un . We consider the following two cases:

Proof.

Case 1: n = m = k = 1. (1, 6)-linear.

If G has no pendant vertex, then by Lemma 2.4, G = H1 , see Figure 3. By (3), H1 is 2-walk

If G has at least one pendant vertex, then for the sake of convenience, we denote the three internal cycles of G0 by x1 x2 , . . . xi x1 , y1 y2 . . . yj y1 , z1 z2 . . . zl z1 . Let u = x1 = y1 = z1 be the vertex in G0 with degree 6. Then by Lemma 3.2 and symmetry, we consider the following three cases: Subcase 1: i = 3 and d(x2 ) = d(x3 ) = 2. We have S(x2 ) = d(x1 )+d(x3 ) > 8. We claim that for y1 y2 . . . yj y1 , z1 z2 . . . zl z1 , we also have j = l = 3 and d(y2 ) = d(y3 ) = d(z2 ) = d(z3 ) = 2. Otherwise, without loss of generality, assume that j 6= 3 and d(y2 ) = d(y3 ) = 2 do not hold. By Lemma 3.2, we have j = 4, d(y2 ) = d(y4 ) = 3, d(y3 ) = 2 or j = 5, d(y2 ) = d(y5 ) = 4, d(y3 ) = d(y4 ) = 2. In both cases, we have d(x1 ) = d(y1 ) = d(z1 ) = d(u) = 6 and d(x2 ) = d(y2 ) = 2. So by (2), S(x2 ) = S(y2 ). On the other hand, by (1), S(x2 ) 6= S(y2 ), a contradiction. Hence all the pendant vertices are adjacent to vertex u and d(u) = a + b > 6. Applying (2) with (v, u) = (u1 , x), we have a = (a + b − 6 + 12 − (a + b))/(a + b − 1) < 2. This is impossible by Lemma 2.5 (iii). Subcase 2: i = 5, d(x1 ) = 6, d(x2 ) = d(x5 ) = 4 and d(x3 ) = d(x4 ) = 2. By symmetry and Subcase 1, we have d(y2 ), d(yj ), d(z2 ), d(zl ) ∈ {3, 4}. For the pendant vertex x adjacent to x2 , by (1) and (2), we have S(x) = a + b = 4, S(x3 ) = 2a + b = 6. So we have a = 2, b = 2. For the vertex u, S(x1 ) = ad(x1 ) + b = 14 = 4 + 4 + d(y2 ) + d(yj ) + d(z2 ) + d(zl ). So d(y2 ) + d(yj ) + d(z2 ) + d(zl ) = 6, which is impossible since d(y2 ), d(yj ), d(z2 ), d(zl ) ∈ {3, 4}.

1805

Tricyclic graphs with exactly two main eigenvalues

Subcase 3: i = 4, d(x1 ) = 6, d(x2 ) = d(x4 ) = 3 and d(x3 ) = 2. By symmetry and Subcases 1 and 2, we have j = l = 4, d(y2 ) = d(y4 ) = d(z2 ) = d(z4 ) = 3 and d(y3 ) = d(z3 ) = 2. G ∼ = H2 , see Figure 3. It is easy to see that H2 is 2-walk (3, 0)-linear. Case 2: n ≥ 2. Then G0 = T1 , see Figure 2. We consider the following two cases: Subcase 1: G has no pendant vertex. Then S(x1 ) = 2 + d(w1 ) = S(x5 ) = 5 by (1) and (2). Hence d(w1 ) = 3. It implies that k ≥ 2. Similarly, we have d(v1 ) = 3 and m ≥ 2. By Lemma 2.4, we have n, m, k ∈ {2, 4}. Without loss of generality, suppose that n ≥ m ≥ k. If n = 2, then m = k = 2. Hence S(u1 ) = 7, S(u2 ) = 9 by (1). On the other hand, d(u1 ) = d(u2 ) = 3, so S(u1 ) = S(u2 ) by (2), a contradiction. Hence n = 4. Similarly, we have m = k = 4. Therefore G = H3 , see Figure 3. By (3), H3 is 2-walk (1, 3)-linear. Subcase 2: G has at least one pendant vertex. In this case, we show that there is no such graph with exactly two main eigenvalues. Since dG0 (u1 ) = 3, we have a = 2 by Lemma 3.1 (iii). So d(xi ) = 2 for i = 1, . . . , 6 by Lemma 3.1, (iii) and (iv). We claim that m, k ≥ 2. Otherwise, let k = 1. Then S(x1 ) = 2 + d(w1 ) = S(x5 ) = 2 + d(u1 ) by (1) and (2). It follows from Lemma 2.5 (ii) and the fact that dG0 (u1 ) = 6 dG0 (w1 ) that d(w1 ) = d(u1 ) = a + b. Hence S(u1 ) = S(w1 ) by (2). By (1),

S(u1 ) = a + b − 3 + 4 + d(u2 ),

S(w1 ) =

( a + b − 5 + 8 + d(un−1 ) a + b − 4 + 4 + d(vm−1 ) + d(un−1 )

if

m = 1,

if

m ≥ 2.

If m = 1, then d(u2 ) = d(un−1 ) + 2. This is impossible by Lemma 3.1 (i). If m ≥ 2, then d(u2 ) + 1 = d(vm−1 ) + d(un−1 ). Obviously, u2 = un−1 when n = 3 and d(u2 ) = d(un−1 ) when n ≥ 4 by Lemma 3.1 (i). Hence d(vm−1 ) = 1, it contradicts the fact that d(vm−1 ) ≥ dG0 (vm−1 ) = 2. Therefore k ≥ 2. Dually, we have m ≥ 2. Note that d(x1 ) = d(x3 ) = d(x5 ), we have S(x1 ) = 2 + d(w1 ) = S(x3 ) = 2 + d(v1 ) = S(x5 ) = 2 + d(u1 ) by (1) and (2). It implies that d(w1 ) = d(v1 ) = d(u1 ) = 3 or a + b. Let d(u1 ) = 3. Applying (3) with (v, u) = (x5 , x), we have a = 5 − (a + b). So a = 2, b = 1. Furthermore, S(u1 ) = 4 + d(u2 ) = 7 by (1) and (2). Thus d(u2 ) = 3. It follows from Lemma 3.1 (i) that d(ui ) = 3 for 2 ≤ i ≤ n − 1. Similarly, we have d(vi ) = d(wj ) = 3 for 2 ≤ i ≤ m − 1 and 2 ≤ j ≤ k − 1. Note that dG0 (un ) = a + b = 3. We have d(un ) = 3 and S(un ) = 7 by (2). On the other hand, S(un ) = 9 by (1), a contradiction. If d(u1 ) = a + b = 6 3, then a + b ≥ 4 by Lemma 2.5 (iii). Applying (3) with (v, u) = (u1 , x), we have
2 = a + b − 3 + 4 + d(u2 ) − (a + b) /(a + b − 1). Note that dG0 (u2 ) = 2 or 3, we have d(u2 ) = 2(a + b) − 3 > max {a + b, dG0 (u2 )}. It contradicts Lemma 2.5 (ii).

Lemma 3.4. Let G ∈ G with δ(G0 ) ≥ 2 and G0 ∈ T2 , see Figure 1. Then G = Hi for i = 4, 5, 6, 7, see Figure 3, or G ∈ Gj for j = 1, 2, see Figure 4. If G0 ∈ T2 , then dG0 (w1 ), dG0 (r1 ) ∈ {3, 4} and so each internal cycle of G0 has the length equal to 3 by Lemmas 2.4 and 3.1 (iii). Hence G0 = T2 and d(xi ) = 2 for i = 1, . . . , 4, see Figure 2, where k, l ≥ 1, n, m ≥ 2. For convenience, we set wk = v1 = u1 and vm = un = rl . By (1) and (2), S(x1 ) = 2 + d(w1 ) = S(x3 ) = 2 + d(r1 ). Hence d(w1 ) = d(r1 ).

Proof.

If G has no pendant vertex, then k, l ∈ {1, 2, 4} and m, n ∈ {2, 4} by Lemma 2.4. First, let k = 1. Then d(w1 ) = d(r1 ) = 4. So l = 1. Therefore G = Hi for i = 4, 5, see Figure 3. By (3), H4 and H5 are 2-walk (2, 2)-linear and 2-walk (1, 4)-linear, respectively. Next, let k = 2. Then d(w1 ) = d(r1 ) = 3. By (1) and (2), S(r1 ) = 4 + d(r2 ) = S(w1 ) = 7. So d(r2 ) = 3 and l = 2. Similarly, S(u1 ) = 3 + d(u2 ) + d(v2 ) = S(w1 ) = 7. So d(u2 ) = d(v2 ) = 2. Note that n, m = 2 or 4, we have n = m = 4 and d(u3 ) = d(v3 ) = 2. Therefore, G = H6 , see Figure 3. By (3), H6 is 2-walk (2, 1)-linear. Finally, let k = 4. With a similar argument of the case k = 2, we have G = H7 is 2-walk (1, 3)-linear, see Figure 3. If G has at least one pendant vertex, we consider the following two cases:

1806

X. Fan, Y. Luo, X. Gao

Figure 4.

Graphs Gi for i = 1, . . . , 9, where l1 , b ≥ 1, l2 ≥ 0 and max {k1 , k2 } ≥ 1.

Case 1: k = l = 1. Then d(w1 ) = d(r1 ) = 4 or a + b by Lemma 2.5 (ii). Let d(w1 ) = 4. Applying (3) with (v, u) = (x1 , 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(w1 ) = 4 + d(u2 ) + d(v2 ) = 12 by (1) and (2). By Lemma 2.5 (ii), d(u2 ), d(v2 ) ∈ {2, 4, a + b}. Thus d(u2 ) = d(v2 ) = 4. It implies that n = m = 2, which is impossible since G is simple. If a + b = 4, then a = b = 2. So S(w1 ) = 4 + d(u2 ) + d(v2 ) = 10 by (1) and (2). By Lemma 2.5 (ii), d(u2 ), d(v2 ) ∈ {2, 4}. Without loss of generality, suppose that d(u2 ) = 2, d(v2 ) = 4. Then d(vi ) = 4 for 2 ≤ i ≤ m − 1 by Lemma 3.1 (i). For the vertex u2 , S(u2 ) = 4 + d(u3 ) = 6 by (1) and (2). So d(u3 ) = 2. Thus n ≥ 4. Hence n = 4 by Lemma 3.1 (ii). Therefore G ∈ G1 , see Figure 4, where l1 ≥ 1. It is easy to see that any graph G ∈ G1 is 2-walk (2, 2)-linear. Let d(w1 ) = a + b > dG0 (u1 ) = 4. In this case, we show that there is no such graph with exactly two main eigenvalues. Applying (3) with (v, u) = (x1 , x) and (v, u) = (w1 , x), respectively, we have a = 2 and a = a + b − 4 + 4 + d(u2 ) + d(v2 )−
(a + b) /(a + b − 1), respectively. Hence d(u2 )+d(v2 ) = 2(a + b)−2. By Lemma 2.5 (ii) and the fact that d(un ) = d(r1 ) = d(w1 ) = a + b, we have d(u2 ), d(v2 ) ∈ {2, a + b}. If d(u2 ) = 2, d(v2 ) ∈ {2, a + b} or d(u2 ) = a + b, d(u2 ) = 2, then a + b = 3 or 4. It contradicts the fact that a + b > 4. If d(u2 ) = d(v2 ) = a + b, then 2(a + b) − 2 = 2(a + b), a contradiction. Case 2: k ≥ 2. Then a = 2 by Lemma 3.1 (iii). By Lemma 2.5 (ii), d(w1 ) = d(r1 ) = 3 or a + b. We first show that d(w1 ) = d(r1 ) = 3. Otherwise, let d(w1 ) = d(r1 ) = a + b = 6 3, then a + b ≥ 4 by Lemma 2.5 (iii). Applying (3) with
(v, u) = (w1 , x), we have 2 = a + b − 3 + 4 + d(w2 ) − (a + b) /(a + b − 1). Note that a + b ≥ 4 and dG0 (w2 ) = 2 or 3. We have d(w2 ) = 2(a + b) − 3 > max {a + b, dG0 (w2 )}. It contradicts Lemma 2.5 (ii). Hence d(w1 ) = d(r1 ) = 3. It implies that l ≥ 2. Next, applying (3) with (v, u) = (x1 , x), we have a = 5 − (a + b). So a + b = 3 and a = 2, b = 1. For the vertex w1 , S(w1 ) = 4 + d(w2 ) = 7 by (1) and (2). So d(w2 ) = 3. Thus d(wi ) = 3 for 2 ≤ i ≤ k − 1 by Lemma 3.1 (i). Note that dG0 (wk ) = 3. We have d(wk ) = 3 by Lemma 2.5 (ii). Hence d(wi ) = 3 for 1 ≤ i ≤ k. Similarly, we have d(rj ) = 3 for 1 ≤ j ≤ l. For the vertex wk , S(wk ) = 3 + d(u2 ) + d(v2 ) = 7. Note that d(u2 ), d(v2 ) ∈ {2, 3} by Lemma 2.5 (ii). We have d(u2 ) = d(v2 ) = 2. It follows from Lemmas 2.4 and 3.1 that m = n = 4 and d(u3 ) = d(v3 ) = 2. Therefore G ∈ G2 , see Figure 4, where max {k1 , k2 } ≥ 1. It is easy to see that any graph G ∈ G2 is 2-walk (2, 1)-linear.

Lemma 3.5. Let G ∈ G with δ(G0 ) ≥ 2 and G0 ∈ T3 , see Figure 1. Then G = H8 , see Figure 3.

1807

Tricyclic graphs with exactly two main eigenvalues

If G0 ∈ T3 , then dG0 (r1 ) ∈ {3, 5} and so the internal cycle of G0 has the length equal to 3 by Lemmas 2.4 and 3.1. Hence G0 = T3 , see Figure 2, where n, m, k ≥ 2, l ≥ 1. For convenience, we set u1 = v1 = w1 and un = vm = wk = rl .

Proof.

We first show that G contains at least one pendant vertex. On the contrary, suppose that G has no pendant vertex. Then n, m, k, l ≤ 4 by Lemma 2.4. Without loss of generality, suppose that n ≥ m ≥ k. If l = 1, then S(x1 ) = 7 and S(u2 ) = 5 or 8 by (1). So S(u2 ) = 6 S(x1 ). On the other hand, S(u2 ) = S(x1 ) by (2), a contradiction. If l ≥ 2, then d(un ) = 4, d(r1 ) = 3. So S(x1 ) = 5 and S(un−1 ) = 6 or 7 by (1). On the other hand, S(x1 ) = S(un−1 ) by (2), a contradiction. Therefore, G has at least one pendant vertex. We consider the following two cases: Case 1: l = 1. By Lemma 3.1 (iv), d(x1 ) = d(x2 ) = 3 or d(x1 ) = d(x2 ) = 2. If d(x1 ) = d(x2 ) = 3, then a = 3, b = 0, d(un ) = 5 by Lemma 3.1 (iv). So d(u1 ) = 3 6= d(un ) by Lemma 2.5 (ii). It follows from Lemma 3.1 (i) that n, m, k ≤ 3. Without loss of generality, suppose that n = m = 3, k = 2 or 3. Then S(u3 ) = 6 + d(u2 ) + d(v2 ) + d(wk−1 ) = 15 by (1) and (2). Note that d(u2 ), d(v2 ), d(wk−1 ) = 2 or 3 by Lemma 2.5 (ii). We have d(u2 ) = d(v2 ) = d(wk−1 ) = 3. So S(u1 ) = 6 + d(w2 ) = 9 by (1) and (2). Thus d(w2 ) = 3. It implies that k = 3. Therefore G = H8 , see Figure 3. By (3), H8 is 2-walk (3, 0)-linear. If d(x1 ) = d(x2 ) = 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} ≥ 4. Without loss of generality, suppose that n ≥ 4. Then d(u1 ) = d(un ) and d(ui ) = d(u2 ) 6 dG0 (un ). We have d(u1 ) = d(un ) = a + b ≥ dG0 (un ) = 5 by for 2 ≤ i ≤ n − 1 by Lemma 3.1 (i). Note that dG0 (u1 ) = Lemma 2.5 (ii). Hence S(u1 ) = a + b − 3 + d(u2 ) + d(v2 ) + d(w2 ),

S(un ) = a + b − 5 + 4 + d(un−1 ) + d(vm−1 ) + d(wk−1 ).

We next show that d(v2 ) = d(vm−1 ). If m = 2, then v2 = un , vm−1 = u1 . So d(v2 ) = d(un ) = d(u1 ) = d(vm−1 ). If m = 3, clearly, d(v2 ) = d(vm−1 ). If m ≥ 4, then d(v2 ) = d(vm−1 ) by Lemma 3.1 (i). Therefore d(v2 ) = d(vm−1 ) for all m ≥ 2. Similarly, we have d(w2 ) = d(wk−1 ) for all k ≥ 2. Hence S(u1 ) = 6 S(un ). On the other hand, S(u1 ) = S(un ) by (2), a contradiction. Subcase 2: max {n, m, k} ≤ 3. Without loss of generality, suppose that n = m = 3 and k = 2 or 3. We claim that d(u2 ) = a + b. Otherwise, let d(u2 ) = dG0 (u2 ) = 2. Then d(u1 ) + d(u3 ) = S(u2 ) = S(x1 ) = 2 + d(u3 ) by (1) and (2), which is impossible since d(u1 ) ≥ dG0 (u1 ) = 3. Hence d(u2 ) = a + b. Similarly, we have d(v2 ) = a + b. Note that d(u3 ) ∈ {a + b, 5} by Lemma 2.5 (ii). Let d(u3 ) = a + b ≥ dG0 (u3 ) = 5. Applying Lemma 2.5 (iv) with C = u1 u2 u3 v2 u1 , we have d(u1 ) 6= a + b. So d(u1 ) = 3. From (3) with (v, u) = (u1 , x) and (v, u) = (x1 , x), we get a = (a + b + d(w2 ))/2 and a = 2, respectively. Hence d(w2 ) = 4 − (a + b) < 0, a contradiction. If d(u3 ) = dG0 (u3 ) = 5= 6 a + b, then a = 7 − (a + b) by applying (3) with (v, u) = (x1 , 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(u2 ) = d(u1 ) + 6 = 11 by (1) and (2). This is impossible since d(u1 ) = 3 by Lemma 2.5 (ii). If a + b = 4, then a = 3, b = 1. Thus S(u2 ) = d(u1 ) + 7 = 13 by (1) and (2). This is also impossible since d(u1 ) = 3 or 4. Case 2: l ≥ 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(x1 ) = d(x2 ) = 2. Applying (3) with (v, u) = (x1 , x), we have 2 = 2 + d(r1 ) − (a + b). So d(r1 ) = a + b.
From (3) with (v, u) = (r1 , x) we get 2 = a + b − 3 + 4 + d(r2 ) − (a + b) /(a + b − 1). Hence d(r2 ) = 2(a + b) − 3. By Lemma 2.5 (ii), d(r2 ) ∈ {2, 4, a + b}. If d(r2 ) = 2 or 4, then a + b is not an integer, a contradiction. If d(r2 ) = a + b, then a + b = 3. So a = 2, b = 1. By Lemmas 2.5 (ii) and 3.1 (i), we have d(rl ) = 4 and d(rl−1 ) = d(r2 ) = 3. Hence S(rl ) = 3 + d(un−1 ) + d(wk−1 ) + d(vm−1 ) = 9 by (1) and (2). It follows that d(un−1 ) = d(wk−1 ) = d(vm−1 ) = 2. Thus S(un−1 ) = 5 by (2). On the other hand, S(un−1 ) = 4 + d(un−2 ) ≥ 6 by (1), a contradiction.

Lemma 3.6. Let G ∈ G with δ(G0 ) ≥ 2 and G0 ∈ T4 , see Figure 1. Then G = Hi for i = 9, 10, 11, see Figure 3, or G ∈ G3 , see Figure 4.

1808

X. Fan, Y. Luo, X. Gao

If G0 ∈ T4 , then dG0 (w1 ) ∈ {3, 4} and so the internal cycle of G0 has the length equal to 3 by Lemmas 2.4 and 3.1 (iii). Hence G0 = T4 , see Figure 2, where k ≥ 1 and p, q, n, m ≥ 2. For convenience, we set u1 = v1 = s1 , un = vm = t1 and sp = tq = wk .

Proof.

If G has no pendant vertex. Without loss of generality, we may assume that n ≥ m, p ≥ q and consider the following two cases: Case 1: k = 1. Then S(x1 ) = 6 by (1). We claim that p = 2. Otherwise, let p ≥ 3. Then d(s2 ) = 2 and S(s2 ) = 5 or 7 by (1). So S(x1 ) = 6 S(s2 ). On the other hand, S(x1 ) = S(s2 ) by (2), a contradiction. Hence p = 2. Similarly, we have q = 2, n = 3, m = 2 or 3. If m = 2, then applying (3) with (v, u) = (w1 , u2 ) and (v, u) = (w1 , u1 ), respectively, we have a = 2 and a = 1, respectively. A contradiction. If m = 3, then G = H9 , see Figure 3. By (3), H9 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(w1 ) = 7 = S(w2 ) = 3 + d(sp−1 ) + d(tq−1 ) by (1) and (2). So d(s2 ) = d(t2 ) = 2. It implies that p = q = 4. Hence n = 4, m = 2. Otherwise, let m = n = 4. Then S(u1 ) = 6 6= S(w1 ) = 7 by (1). On the other hand, S(u1 ) = S(w1 ) by (2), a contradiction. Therefore n = 4, m = 2 and G = H10 , see Figure 3. By (3), H10 is 2-walk (2, 1)-linear. If k = 4, with a similar argument, we have G = H11 is 2-walk (1, 3)-linear, see Figure 3. If G has at least one pendant vertex, then k > 1. Otherwise, suppose that k = 1. Then d(w1 ) = 4 or a + b by Lemma 2.5 (ii). Let d(w1 ) = 4 6= a + b. Applying (3) with (v, u) = (x1 , x) we get a = 6 − (a + b). It follows from Lemma 2.5 (iii) that a = 3, b = 0. So S(w1 ) = 4 + d(sp−1 ) + d(tq−1 ) = 12 by (1) and (2). This is impossible since d(sp−1 ), d(tq−1 ) = 2 or 3 by Lemma 2.5 (ii). Let now d(w1 ) = a + b ≥ 4. Apply (3) with (v, u) = (x1 , x) and (v, u) = (w1 , x).
We get a = 2 and a = a + b − 4 + 4 + d(tq−1 ) + d(sp−1 ) − (a + b) /(a + b − 1), respectively. Thus d(tq−1 ) + d(sp−1 ) = 2(a + b) − 2.

(6)

Note that d(tq−1 ), d(sp−1 ) ∈ {2, 3, a + b}. We consider the following five cases by symmetry: • If d(tq−1 ) = d(sp−1 ) = 2, then a + b = 3. This contradicts the fact that a + b ≥ 4. • If d(tq−1 ) = 2, d(sp−1 ) = 3, then a + b = 3.5. This contradicts Lemma 2.2. • If d(tq−1 ) = 2, d(sp−1 ) = a + b, then a + b = 4 by (6). Note that a = 2. We have b = 2 and d(sp−1 ) = d(w1 ) = 4. By Lemma 3.1, d(si ) = 4 for 2 ≤ i ≤ p − 1. So S(s2 ) = 6 + d(u1 ) = 10 by (1) and (2). Thus d(u1 ) = 4. Similarly, we have d(un ) = 4. By (1) and (2), S(u1 ) = 5 + d(u2 ) + d(v2 ) = 10. This is impossible since d(u2 ), d(v2 ) = 2 or 4. • If d(tq−1 ) = 3, d(sp−1 ) = a + b, then a + b = 5 by (6). Recall that a = 2, we have b = 3 and d(w1 ) = 5. Note that d(tq−1 ) = 3 6= a + b. We have q = 2. Thus S(tq−1 ) = 9 = 5 + d(un−1 ) + d(vn−1 ) by (1) and (2). By Lemma 2.5 (ii), d(un−1 ), d(vn−1 ) ∈ {2, 3, 5}. Hence d(un−1 ) = d(vn−1 ) = 2. Therefore S(un−1 ) = 3 + d(un−2 ) = 7, which is impossible since d(un−2 ) ∈ {2, 3, 5}. • If d(tq−1 ) = d(sp−1 ) = a + b, then 2(a + b) = 2(a + b) − 2 by (6), a contradiction. Hence k > 1. It follows from Lemma 3.1 (iii) that a = 2 and d(x1 ) = d(x2 ) = 2. From (3) with (v, u) = (x1 , x) it follows
2 = 2 + d(w1 ) − (a + b). So d(w1 ) = a + b. By (3) with (v, u) = (w1 , x), 2 = a + b − 3 + 4 + d(w2 ) − (a + b) /(a + b − 1). Thus d(w2 ) = 2(a + b) − 3 ≥ 3. Note that d(w2 ) ∈ {2, 3, a + b} by Lemma 2.5 (ii). We have d(w2 ) = 3 or a + b. It follows that a + b = 3 and a = 2, b = 1. By Lemma 3.1 (i), d(wi ) = d(w2 ) = 3 for 2 ≤ i ≤ k − 1. By Lemma 2.5 (ii), d(w1 ) = d(wk ) = d(u1 ) = d(un ) = 3. For the vertex wk , we have S(wk ) = 3 + d(sp−1 ) + d(tq−1 ) = 7. It follows from Lemma 2.5 (ii) that d(sp−1 ) = d(tq−1 ) = 2 and p, q ≥ 3. Hence p = q = 4 and d(s2 ) = d(t2 ) = 2 by Lemmas 2.4 and 3.1 (ii). For the vertex u1 , we have S(u1 ) = 2 + d(v2 ) + d(u2 ) = 7. Note that d(u2 ), d(v2 ) ∈ {2, 3}. We may assume that d(v2 ) = 2, d(u2 ) = 3 by symmetry. It follows from Lemmas 2.4 and 3.1 (ii) that m = 4, d(v3 ) = 2 and d(ui ) = 3 for 2 ≤ i ≤ n − 1. Therefore G ∈ G3 , see Figure 4, where max {k1 , k2 } ≥ 1. It is easy to see that any graph G ∈ G3 is 2-walk (2, 1)-linear.

Lemma 3.7. There is no graph G ∈ G with δ(G0 ) ≥ 2 and G0 ∈ T5 , see Figure 1.

1809

Tricyclic graphs with exactly two main eigenvalues

Proof. By way of contradiction, suppose that G ∈ G with G0 ∈ T5 . Let G0 = T5 , see Figure 2, where n, m, k, p, q ≥ 2. For convenience, we set u1 = v1 = s1 , un = wk = tq , vm = sp = w1 = t1 and consider the following two cases: Case 1: there is a vertex v ∈ {vm−1 , sp−1 , w2 , t2 } such that dG0 (v) = 2 and d(v) = a + b. Without loss of generality, let v = vm−1 . Then d(vi ) = a + b for 2 ≤ i ≤ m − 1 by Lemma 3.1 (i). In particular, a ≥ 2, a + b ≥ 3 by Lemma 2.5 (iii). We first show that d(u1 ) = d(w1 ) = a + b. If m ≥ 4, then d(u1 ) = d(w1 ) by Lemma 3.1 (i). Note that dG0 (u1 ) = 6 dG0 (w1 ). We have d(u1 ) = d(w1 ) = a + b by Lemma 2.5 (ii). Let now m = 3. From (3) with (v, u) = (v2 , x), a=

a + b − 2 + d(u1 ) + d(w1 ) − (a + b) d(u1 ) + d(w1 ) − 2 = . a+b−1 a+b−1

By Lemma 2.5 (ii), d(u1 ) = 3 or a + b and d(w1 ) = 4 or a + b. If d(u1 ) = 3, d(w1 ) = 4, then a = 5/(a + b − 1). Note that a ≥ 2 is an integer. We have a + b = 2. It contradicts the fact that a + b ≥ 3. If d(u1 ) = 3, d(w1 ) = a + b ≥ 4, then a = 1 + 2/(a + b − 1) < 2, a contradiction. If d(u1 ) = a + b ≥ 3, d(w1 ) = 4 6= a + b, then a = 1 + 3/(a + b − 1) is not an integer, a contradiction. Hence d(u1 ) = d(w1 ) = a + b. By Lemma 2.5 (iv) applied to C = u1 v2 . . . vm−1 w1 sp−1 . . . s2 u1 , we get p ≥ 3 and d(si ) 6= a + b for some 2 ≤ i ≤ p − 1. It follows from Lemmas 2.5 (ii) and 3.1 (i) that d(si ) = 2 for 2 ≤ i ≤ p − 1. By (3) with (v, u) = (v2 , x) and (v, u) = (u1 , x), we have a = 2 and a = 1 + d(u2 )/(a + b − 1), respectively. This together with Lemma 2.5 (ii) and the fact that a + b ≥ dG0 (w1 ) = 4 implies that d(u2 ) = a + b − 1 = dG0 (u2 ) ≥ 3. Hence n = 2, d(u2 ) = dG0 (u2 ) = 3. Therefore a + b = 4 and a = b = 2. By (1) and (2), S(u2 ) = 4 + d(wk−1 ) + d(tq−1 ) = 8. By Lemma 2.5 (ii), d(wk−1 ), d(tq−1 ) = 2 or 4. Thus d(wk−1 ) = d(tq−1 ) = 2. Hence S(wk−1 ) = 3 + d(wk−2 ) = 6 by (1) and (2), which is impossible since d(wk−2 ) = 2 or 4. Case 2: for any vertex v ∈ {vm−1 , sp−1 , w2 , t2 }, dG0 (v) = 3 or d(v) = 2. It follows from Lemma 2.4 that m, k, p, q ≤ 4. Without loss of generality, suppose that m ≥ p, k ≥ q. Hence m, k = 3 or 4. Subcase 1: max {m, k} = 4. Without loss of generality, suppose that m = 4. Then d(u1 ) = d(w1 ) by Lemma 3.1 (i). Note that dG0 (u1 ) 6= dG0 (w1 ). We have d(u1 ) = d(w1 ) = a + b ≥ dG0 (w1 ) = 4 by Lemma 2.5 (ii). Thus G has at least one pendant vertex. Apply (3) with (v, u) = (v2 , x) and (v, u) = (u1 , x). We have a = 2 and a = a + b − 3 + 2 + d(s2 ) + d(u2 )−
(a + b) /(a + b − 1), respectively. Hence d(s2 ) + d(u2 ) = 2(a + b) − 1. If p > 2, then d(s2 ) = 2. It follows from the fact that dG0 (u2 ) = 2 or 3 and a + b ≥ 4 that d(u2 ) = 2(a + b) − 3 > max {a + b, dG0 (u2 )}, which is impossible by Lemma 2.5 (ii). If p = 2, then d(s2 ) = d(w1 ) = a+b. So d(u2 ) = a+b−1 ≥ 3. It follows that n = 2, d(u2 ) = dG0 (u2 ) = 3 and a + b = 4. Hence a = b = 2. By (2), S(wk−1 ) = 6. On the other hand, S(wk−1 ) = d(wk−2 ) + d(u2 ) = 5 or 7 by (1), a contradiction. Subcase 2: m = k = 3. S(u1 ) = S(un ) by (2).

Then d(w1 ) + d(u1 ) = S(v2 ) = S(w2 ) = d(w1 ) + d(un ) by (1) and (2). So d(u1 ) = d(un ). Thus

We claim that p = q = 2 or 3. Otherwise, let p 6= q. Without loss of generality, suppose that p = 3, q = 2. Then S(u1 ) = d(u1 ) − 3 + 4 + d(u2 ) and S(un ) = d(un ) − 3 + 2 + d(w1 ) + d(un−1 ). Note that d(u2 ) = d(un−1 ), d(w1 ) > 2. We have S(u1 ) 6= S(un ), a contradiction. Hence p = q = 2 or 3. We consider the following two cases: Subcase 2.1: G has no pendant vertex. Then n = 2. Otherwise, suppose that n > 2. Then d(u2 ) = d(v2 ) = 2. By (1) and (2), 3 + d(u3 ) = S(u2 ) = S(v2 ) = 7. This is impossible since d(u3 ) = 2 or 3. Hence n = 2. Let p = q = 2. Apply (3) for (v, u) = (u1 , v2 ) and (v, u) = (w1 , u1 ), respectively, then a = 2 and a = 1, respectively, a contradiction. If p = q = 3, also applying (3) with (v, u) = (u1 , v2 ) and (v, u) = (w1 , u1 ), respectively, we have a = 0 and a = 1, respectively. Also a contradiction. Subcase 2.2: G has at least one pendant vertex. Then a ≥ 2, a + b ≥ 3. First, let p = q = 3. Applying (3) with (v, u) = (w1 , x), we get a = (d(w1 ) − 4 + 8 − (a + b))/(d(w1 ) − 1). By Lemma 2.5 (ii), d(w1 ) = a + b or 4. It follows that a < 2, a contradiction. Next, suppose that p = q = 2. By Lemma 2.5 (ii), d(w1 ) = a+b or 4. If d(w1 ) = a+b ≥ 4, applying (3) with (v, u) = (w1 , x) and noting that d(u1 ) = d(un ), we have a = 2d(u1 )/(a + b − 1). If d(u1 ) = a + b, then a = 2 + 2/(a + b − 1) is not an

1810

X. Fan, Y. Luo, X. Gao

integer, which is impossible by Lemma 2.2. If d(u1 ) = dG0 (u1 ) = 3 = 6 a + b, then a + b = 4 and a = b = 2. So S(v2 ) = 6 by (2). On the other hand, S(v2 ) = d(u1 ) + d(w1 ) = 7 by (1), a contradiction. If d(w1 ) = 4 6= a + b, then applying (3) with (v, u) = (v2 , x), we have a = 4 + d(u1 ) − (a + b). If d(u1 ) = a + b, then a = 4. For the vertex u1 , we have S(u1 ) = 4(a + b) + b = a + b − 3 + 6 + d(u2 ). It follows that d(u2 ) = 4(a + b) − 7 > max {a + b, dG0 (u2 )}, which is impossible by Lemma 2.5 (ii). If d(u1 ) = 3 6= a + b, then a = 7 − (a + b). Note that a + b 6= 3, 4. We have a + b = 5 and a = 2, b = 3 by Lemma 2.5 (iii). By (1) and (2), S(w1 ) = 11 = 4 + d(u1 ) + d(un ). This is impossible since d(u1 ) = d(un ).

Lemma 3.8. Let G ∈ G with δ(G0 ) ≥ 2 and G0 ∈ T6 . Then G = Hi for i = 12, . . . , 17, see Figure 3, or G ∈ G4 , see Figure 4.

Proof.

Let G0 = T6 , see Figure 2, where n, m, p, k ≥ 2. For convenience, we set u1 = v1 = w1 = s1 and un = vm =

w k = sp . Case 1: there is a vertex v ∈ {u2 , v2 , w2 , s2 } such that dG0 (v) = 2 and d(v) = a + b. suppose that v = u2 . From (3) with (v, u) = (u2 , x), we get a=

a + b − 2 + d(u1 ) + d(u3 ) − (a + b) d(u1 ) + d(u3 ) − 2 = . a+b−1 a+b−1

Without loss of generality,

(7)

By Lemma 2.5 (ii), d(u1 ), d(u3 ) = 4 or a + b. We consider the following three cases: Subcase 1: d(u1 ) = d(u3 ) = a + b. Then a = 2 by (7). We now show that d(ui ) = a + b for 1 ≤ i ≤ n. If n = 3, then obviously, d(ui ) = a + b for 1 ≤ i ≤ n. If n ≥ 4, then d(ui ) = d(u2 ) = a + b for 1 < i < n and d(un ) = d(u1 ) = a + b by Lemma 3.1 (i). Hence d(ui ) = a + b for 1 ≤ i ≤ n. By Lemma 2.5 (iv) applied to C = u1 u2 . . . un vm−1 . . . v2 u1 , we have d(vi ) 6= a + b for some 2 ≤ i ≤ m − 1. It follows from Lemmas 2.5 (ii) and 3.1 (i) that m ≥ 3 and d(vi ) = 2 for all 2 ≤ i ≤ m − 1. Thus S(v2 ) = 2a + b = a + b + d(v3 ). Note that a = 2 and d(v3 ) = 2, so m ≥ 4. It follows from Lemma 3.1 (ii) that m = 4. Similarly, we have k = p = 4 and d(w2 ) = d(w3 ) = d(s2 ) = d(s3 ) = 2. For the vertex u1 , S(u1 ) = 2(a + b) + b = a + b − 4 + 6 + a + b by (1) and (2), hence b = 2. It follows that d(ui ) = a + b = 4 for 1 ≤ i ≤ n. Therefore G ∈ G4 , see Figure 4, where l1 ≥ 1. It is easy to see that any graph G ∈ G4 is 2-walk (2, 2)-linear. Subcase 2: d(u1 ) = a + b, d(u3 ) = 4 or d(u1 ) = 4, d(u3 ) = a + b = 6 4. by (7), a contradiction.

Then a = 1 + 3/(a + b − 1) is not an integer

Subcase 3: d(u1 ) = d(u3 ) = 4 = 6 a + b. Then n = 3 and a = 6/(a + b − 1). It follows from Lemma 2.5 (iii) that a + b = 3 and a = 3, b = 0. Thus d(u2 ) = a + b = 3. For the vertex u1 , S(u1 ) = 12 = 3 + d(v2 ) + d(w2 ) + d(s2 ) by (1) and (2). Note that d(v2 ), d(w2 ), d(s2 ) ∈ {2, 4, a + b}. By symmetry, we have either d(v2 ) = d(w2 ) = d(s2 ) = a + b = 3 or d(v2 ) = 2, d(w2 ) = 3, d(s2 ) = 4. If d(v2 ) = d(w2 ) = d(s2 ) = 3, then S(v2 ) = 9 = 5 + d(v3 ). Thus d(v3 ) = 4 6= a + b. It implies that m = 3. Similarly, we have k = p = 3. Therefore G = H12 , see Figure 3. By (3), H12 is 2-walk (3, 0)-linear. If d(v2 ) = 2, d(w2 ) = 3, d(s2 ) = 4, then p = 2 and S(w2 ) = 9 = 4 + 1 + d(w3 ), S(v2 ) = 6 = 4 + d(v3 ). So d(w3 ) = 4 and d(v3 ) = 2. This implies that k = 3 and S(v3 ) = 6 = 2 + d(v4 ). Thus d(v4 ) = 4 and m = 4. Thus G ∼ = H13 , see Figure 3. It is easy to see that H13 is 2-walk (3, 0)-linear. Case 2: for any vertex v ∈ {u2 , v2 , w2 , s2 }, dG0 (v) = 4 or d(v) = 2. By Lemma 2.4, n, m, p, k ≤ 4. Without loss of generality, suppose that n ≥ m ≥ p ≥ k. Then n ≥ m ≥ p ≥ 3 and d(u2 ) = d(v2 ) = d(s2 ) = 2. By (1) and (2), S(u2 ) = d(u1 ) + d(u3 ) = S(v2 ) = d(u1 ) + d(v3 ). Thus d(v3 ) = d(u3 ). It implies that m = n. Similarly, we have p = n and k = n or 2. Hence k = p = m = n ∈ {3, 4} or k = 2, p = m = n ∈ {3, 4}. If G has no pendant vertex, then G = Hi for i = 14, . . . , 17, see Figure 3. By (3), H14 is 2-walk (1, 6)-linear, H15 is 2-walk (0, 8)-linear, H16 is 2-walk (2, 2)-linear and H17 is 2-walk (1, 4)-linear. If G has at least one pendant vertex x, then x ∈ N(u1 ) or x ∈ N(un ). Without loss of generality, suppose that x ∈ N(u1 ), then d(u1 ) = a + b ≥ 5. Applying (3) with (v, u) = (u1 , x), we have a = (d(w2 ) + 2)/(a + b − 1). By Lemma 2.5 (ii), d(w2 ) = 2, 4 or a + b. It implies that a < 2. This is impossible by Lemma 2.5 (iii).

1811

Tricyclic graphs with exactly two main eigenvalues

Lemma 3.9. Let G ∈ G with δ(G0 ) ≥ 2 and G0 ∈ T7 , see Figure 1. Then G = Hi for i = 18 . . . , 25, see Figure 3, or G ∈ Gj for j = 5, 6, 7, see Figure 4.

Proof.

Let G0 = T7 , see Figure 2, where n, m, k, l, p, q ≥ 2. For convenience, we set u1 = w1 = s1 , un = wk = t1 , v1 = r1 = sp and vm = rl = tq .

If G has no pendant vertex, then n, m, k, l, p, q ≤ 4 by Lemma 2.4. Without loss of generality, suppose that n ≥ k, m ≥ l, p ≥ q, then n = 3 or 4. By (1) and (2), S(u1 ) = d(u2 ) + d(w2 ) + d(s2 ) = S(un ) = d(un−1 ) + d(wk−1 ) + d(t2 ). Note that d(u2 ) = d(un−1 ), d(w2 ) = d(wk−1 ). We have d(s2 ) = d(t2 ). 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 = Hi for i = 18, 19, 20, 21, see Figure 3. If n = 4, then m = 4, k, p = 2 or 4 by Lemma 2.4. Hence G = Hj for j = 22, 23, 24, 25, see Figure 3. By (3), H18 is 2-walk (2, 2)-linear, H19 and H20 are 2-walk (1, 4)-linear, H21 is 2-walk (0, 6)-linear, H22 is 2-walk (3, −1)-linear, H23 and H24 are 2-walk (2, 1)-linear, H25 is 2-walk (1, 3)-linear. If G has at least one pendant vertex, then a ≥ 2, a + b ≥ 3. We first show that d(v1 ) = d(vm ). If max {m, l} ≥ 4, then d(v1 ) = d(vm ) by Lemma 3.1 (i). Let m, l ≤ 3. By way of contradiction, suppose that d(v1 ) = 6 d(vm ). By Lemma 2.5 (ii), we may assume that d(v1 ) = a + b > 3, d(vm ) = 3 without loss of generality. By (3) with (v, u) = (v1 , v3 ),  d(sp−1 ) − d(tq−1 )    a+b−3 a=   1 + d(sp−1 ) − d(tq−1 ) a+b−3

if

m = 3, l = 2 or

if

m = 3, l = 3.

m = 2, l = 3,

By Lemma 2.5 (ii), d(sp−1 ), d(tq−1 ) = 2, 3 or a + b. If m = 3, l = 2 or m = 2, l = 3, then d(sp−1 ) = a + b, d(tq−1 ) = 2 since a ≥ 2, a + b ≥ 3. So a = 1 + 1/(a + b − 3). It implies that a + b = 4 and a = b = 2. By (1) and (2), S(v3 ) = 6 + d(v2 ) = 8. So d(v2 ) = 2 and S(v2 ) = 6 by (2). On the other hand, S(v2 ) = 7 by (1), a contradiction. If m = l = 3, then d(sp−1 ) = a + b 6= 3, d(tq−1 ) = 3 or d(sp−1 ) = a + b, d(tq−1 ) = 2 since a ≥ 2, a + b ≥ 3. If d(sp−1 ) = a + b = 6 3, d(tq−1 ) = 3, then a + b ≥ 4 and a = 2. Thus b ≥ 2. By (1) and (2), S(v3 ) = 6 + b = d(v2 ) + d(r2 ) + 3, which is impossible since d(v2 ), d(r2 ) = 2 or 2 + b and b ≥ 2. If d(sp−1 ) = a + b, d(tq−1 ) = 2, then a = 2 + 1/(a + b − 3). It implies that a + b = 4 and a = 3, b = 1. By (1) and (2), S(v3 ) = d(v2 ) + d(r2 ) + 2 = 10. Note that d(v2 ), d(r2 ) = 2 or 4 by Lemma 2.5 (ii), we have d(v2 ) = d(r2 ) = 4. Thus S(v2 ) = 13 by (2). On the other hand, S(v2 ) = 9 by (1), a contradiction. Hence d(v1 ) = d(vm ). By Lemma 2.5 (ii), we consider the following two cases. Case 1: d(v1 ) = d(vm ) = 3 6= a + b. Then a + b ≥ 4. Note that max {m, l} ≥ 3. Without loss of generality, suppose that m ≥ 3. By Lemma 2.5 (ii), we have d(v2 ) = a + b or 2. Let d(v2 ) = a + b. From (3) with (v, u) = (v2 , x), it follows a = (d(v3 ) + 1)/(a + b − 1). By Lemma 2.5 (ii), d(v3 ) = 2, 3 or a + b. This together with a + b ≥ 4 implies that a < 2. It contradicts the fact that a ≥ 2. Let now d(v2 ) = 2. By (3) with (v, u) = (v2 , x), a = 3 + d(v3 ) − (a + b). So d(v3 ) = a + a + b − 3 ≥ 3. If m > 3, then by Lemma 3.1 (i), d(v3 ) = d(v2 ) = 2. Thus m = 3. By assumption, d(v3 ) = 3 and a = 6 − (a + b). Note that a + b ≥ 4, a ≥ 2, hence a + b = 4 and a = b = 2. By (1) and (2), S(v1 ) = 2 + d(r2 ) + d(sp−1 ) = 8. So d(r2 ) + d(sp−1 ) = 6. If l = 2, then d(r2 ) = d(vm ) = 3. So d(sp−1 ) = 3 ∈ / {a + b, 2}. It implies that p = 2 and d(u1 ) = d(sp−1 ) = 3. Similarly, we get q = 2 and d(un ) = 3. By (1) and (2), S(u1 ) = 3 + d(w2 ) + d(u2 ) = 8. Note that d(w2 ), d(u2 ) = 2, 3 or 4 by Lemma 2.5 (ii). It follows that d(u2 ) = 2, d(w2 ) = 3 or d(u2 ) = 3, d(w2 ) = 2. We may suppose that d(u2 ) = 2, d(w2 ) = 3 without loss of generality. Then k = 3 and d(ui ) = 2 for 2 ≤ i ≤ n − 1 by Lemma 3.1 (i). Hence G has no pendant vertex. This is a contradiction. If l ≥ 3, then d(r2 ) = 2 or 4. We claim that d(r2 ) = 2. Otherwise, let d(r2 ) = 4, then S(r2 ) = 10 by (2). This is also impossible since S(r2 ) = 4 − 2 + 3 + d(r3 ) ≤ 9 by (1). Hence d(r2 ) = 2. By (1) and (2), we have S(r2 ) = 2d(r2 ) + 2 = 6 = d(v1 ) + d(r3 ) = 3 + d(r3 ). So d(r3 ) = 3 6= a + b and hence l = 3. Furthermore, we have S(v1 ) = 2d(v1 ) + 2 = 8 = d(v2 ) + d(r2 ) + d(sp−1 ) = 4 + d(sp−1 ). Thus d(sp−1 ) = 4. Thus S(sp−1 ) = 10 by (2). If p > 2, then S(sp−1 ) = 4 − 2 + 3 + d(sp−2 ) ≤ 9 by (1). A contradiction. So p = 2 and sp−1 = u1 . Thus d(u1 ) = d(sp−1 ) = 4.

1812

X. Fan, Y. Luo, X. Gao

Furthermore, by (1) and (2), we have S(u1 ) = 2d(u1 ) + 2 = 10 = 1 + 3 + d(u2 ) + d(w2 ). Hence d(u2 ) + d(w2 ) = 6. Note that d(un ) = d(u1 ) = 4 and a + b = 4, then by Lemma 2.5 (ii), we have d(u2 ) = 2 or 4. Similarly, we have d(w2 ) = 2 or 4. By symmetry, we may assume that d(u2 ) = 2, d(w2 ) = 4. By Lemma 3.1 (i), d(wi ) = 4 for all i = 1, . . . , k. Furthermore, S(u2 ) = 6 = 4 + d(u3 ). Thus d(u3 ) = 2 and S(u3 ) = 6 = 2 + d(u4 ). So d(u4 ) = 4 6= d(u2 ) and hence n = 4. Therefore G ∈ G5 , see Figure 4. It is easy to see that every graph in G5 is 2-walk (2, 2)-linear. Case 2: d(v1 ) = d(vm ) = a + b. Dually, we have d(u1 ) = d(un ) = a + b. Apply Lemma 2.5 (iv) to C = v1 v2 . . . vm rl−1 . . . r2 v1 . We get, without loss of generality, m ≥ 3 and d(vi ) = 6 a + b for some 2 ≤ i ≤ m − 1. So d(vi ) = 2 for all 2 ≤ i ≤ m − 1 by Lemmas 2.5 (ii) and 3.1. From (3) with (v, u) = (v1 , x) and (v, u) = (v2 , x), we have a=

d(r2 ) + d(sp−1 ) − 1 , a+b−1

a = d(v3 ),

(8)

respectively. We claim that m ≥ 4. Otherwise, suppose that m = 3. Then a = d(v3 ) = a + b and d(r2 ) + d(sp−1 ) = a(a + b − 1) + 1 ≥ 3(a + b) − 2 > 2(a + b), which is impossible since d(r2 ), d(sp−1 ) = 2 or a + b by Lemma 2.5 (ii). Hence m ≥ 4. Therefore m = 4 by Lemma 3.1 (ii). Thus a = d(v3 ) = 2. It follows from (8) that d(r2 ) + d(sp−1 ) = 2(a + b) − 1. By Lemma 2.5 (iii), d(r2 ), d(sp−1 ) = 2 or a + b. • If d(r2 ) = d(sp−1 ) = 2, then a + b = 2.5, a contradiction. • If d(r2 ) = d(sp−1 ) = a + b, then 2(a + b) = 2(a + b) − 1, a contradiction. • If d(r2 ) = 2, d(sp−1 ) = a + b, then a + b = 3. So a = 2, b = 1. By Lemma 3.1 (i), d(si ) = d(sp−1 ) = 3 for 2 ≤ i ≤ p − 1. For the vertex u1 , S(u1 ) = 3 + d(u2 ) + d(w2 ) = 7 by (1) and (2). By Lemma 2.5 (ii), d(u2 ), d(w2 ) = 2 or 3. It follows that d(u2 ) = d(w2 ) = 2. So S(u2 ) = 3 + d(u3 ) = 5. Thus d(u3 ) = 2 and n ≥ 4. Hence n = 4 by Lemma 3.1 (ii). Similarly, we have d(w3 ) = d(r2 ) = 2 and k = l = 4. By (1) and (2), S(u4 ) = 4 + d(t2 ) = 7. So d(t2 ) = 3. Hence d(ti ) = 3 for 1 ≤ i ≤ q − 1 by Lemma 3.1 (i). Therefore G ∈ G6 , see Figure 4, where max {k1 , k2 } ≥ 1. It is easy to see that any graph G ∈ G6 is 2-walk (2, 1)-linear. • If d(r2 ) = a + b, d(sp−1 ) = 2, then with a similar argument of the case d(r2 ) = 2, d(sp−1 ) = a + b, we have G ∈ G7 and G is 2-walk (2, 1)-linear, see Figure 4, where max {k1 , k2 } ≥ 1.

Lemma 3.10.

Let G ∈ G with δ(G0 ) ≥ 2 and G0 ∈ T8 . Then G ∼ = Hi for i = 26, . . . , 32, see Figure 3, or G ∈ Gj for j = 8, 9, see Figure 4.

Proof.

Let G0 = T8 , see Figure 2, where n, m, k, l, p, q ≥ 2. For convenience, we set u1 = v1 = w1 , un = t1 = sp , vm = r1 = tq and wk = s1 = rl . Case 1: there is a vertex v ∈ {w2 , v2 , u2 } with dG0 (v) = 2 and d(v) = a + b. Without loss of generality, suppose that v = w2 . Then k ≥ 3 and d(wi ) = a + b for 2 ≤ i ≤ k − 1 by Lemma 3.1 (i). In particular, a ≥ 2, a + b ≥ 3 by Lemma 2.5 (iii). Lemma 2.3 for (v, u) = (w2 , x) implies a = (d(w1 ) + d(w3 ) − 2)/(a + b − 1). By Lemma 2.5 (ii), we have d(w1 ), d(w3 ) = 3 or a + b. If d(w1 ) = d(w3 ) = 3 = 6 a + b, then a + b ≥ 4 and a = 4/(a + b − 1) < 2, a contradiction. If d(w1 ) = a + b, d(w3 ) = 3 or d(w3 ) = a + b, d(w1 ) = 3 and a + b 6= 3, then a = (a + b + 1)/(a + b − 1) = 1 + 2/(a + b − 1) < 2, a contradiction. If d(w1 ) = d(w3 ) = a + b, then a = 2. We claim that a + b = 3. Otherwise, let a + b > 3. For the vertex w1 , S(w1 ) = 2(a + b) + b = a + b − 3 + a + b + d(u2 ) + d(v2 ). Thus d(u2 ) + d(v2 ) = a + b + 1. By Lemma 2.5 (ii), d(u2 ), d(v2 ) = 2, 3 or a + b. Note that a + b > 3. We have d(u2 ) = 2, d(v2 ) = 3 or d(u2 ) = 3, d(v2 ) = 2 or d(u2 ) = d(v2 ) = 3. Without loss of generality, we consider the following two cases: • If d(u2 ) = 2, d(v2 ) = 3, then a + b = 4 and m = 2. Note that a = 2. We have b = 2. If k ≥ 4, then d(wk ) = d(w1 ) = 4 by Lemma 3.1 (i). If k = 3, then d(wk ) = d(w3 ) = 4. So d(r3 ) = 2 or 4 by Lemma 2.5 (ii). On the other hand, S(v2 ) = 4 + d(r2 ) + d(tq−1 ) = 8 by (1) and (2). So d(r2 ) = d(tq−1 ) = 2. By (1) and (2), S(r2 ) = 6 = 3 + d(r3 ). Thus d(r3 ) = 3, a contradiction.

1813

Tricyclic graphs with exactly two main eigenvalues

• If d(u2 ) = d(v2 ) = 3, then a + b = 5 and m = n = 2. Note that a = 2. We have b = 3. By (1) and (2), S(v2 ) = 5 + d(r2 ) + d(tq−1 ) = 9. Thus d(r2 ) = d(tq−1 ) = 2. Hence S(r2 ) = 7 = 3 + d(r3 ). This is impossible since d(r3 ) ∈ {2, 3, 5}. Therefore a + b = 3 and a = 2, b = 1. By (1) and (2), S(w1 ) = 7 = 3 + d(v2 ) + d(u2 ). So d(v2 ) = d(u2 ) = 2. Hence S(v2 ) = 5 = 3 + d(v3 ). It follows that d(v3 ) = 2 and m ≥ 4. Therefore m = 4 by Lemma 3.1 (ii). Similarly, we have n = l = p = 4, d(u2 ) = d(u3 ) = d(r2 ) = d(r3 ) = d(s2 ) = d(s3 ) = 2 and d(ti ) = 3 for 2 ≤ i ≤ q − 1. Therefore G ∈ G9 , see Figure 4, where max {k1 , k2 } ≥ 1. It is easy to see that any graph G ∈ G9 is 2-walk (2, 1)-linear. Case 2: for any vertex v ∈ {w2 , v2 , u2 }, we have dG0 (v) = 3 or d(v) = 2. If G has no pendant vertex, then n, m, k, l, p, q ≤ 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} ≥ 3. Without loss of generality, suppose that n ≥ 3. We consider the following two cases: Subcase 1: n = 3. Then S(u2 ) = 6 and m, k, l, p, q = 2 or 3 by Lemma 2.4. If m = k = 2, then S(u1 ) = 8 = S(u3 ) = 2 + d(t2 ) + d(sp−1 ). So d(t2 ) = d(sp−1 ) = 3 and hence p = q = 2. Similarly, S(u1 ) = 8 = S(v2 ) = 6 + d(r2 ). Thus d(r2 ) = 2 and l = 3. Therefore G = H26 , see Figure 3. By (3), H26 is 2-walk (2, 2)-linear. With a similar argument, we have: If m = 2, k = 3 or m = 3, k = 2, then G = H27 is 2-walk (1, 4)-linear, see Figure 3. If m = k = 3, then G = H28 is 2-walk (0, 6)-linear, see Figure 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 = H29 is 2-walk (3, −1)-linear, see Figure 3. If m = 2, k = 4 or m = 4, k = 2, then G = H30 is 2-walk (2, 1)-linear, see Figure 3. If m = k = 4, then G = H31 is 2-walk (1, 3)-linear, see Figure 3. If G has at least one pendant vertex x, then x ∈ N(v) for v ∈ {w1 , vm , un , wk , ri1 , ti2 , si3 }, where 2 ≤ i1 ≤ l − 1, 2 ≤ i2 ≤ q − 1, 2 ≤ i3 ≤ p − 1. If v ∈ {ri1 , ti2 , si3 }, then with a similar argument of Case 1, we have G ∈ G9 . Hence we may suppose that v ∈ {w1 , vm , un }. In particular, assume that x ∈ N(w1 ) without loss of generality. Then d(w1 ) = a + b ≥ 4 and d(u) = dG0 (u) for u ∈ {ri1 , ti2 , si3 }, where 2 ≤ i1 ≤ l − 1, 2 ≤ i2 ≤ q − 1, 2 ≤ i3 ≤ p − 1. Apply Lemma 2.3 with (v, u) = (w1 , x). We get a=

a + b − 3 + d(u2 ) + d(v2 ) + d(w2 ) − (a + b) d(u2 ) + d(v2 ) + d(w2 ) − 3 = . a+b−1 a+b−1

Note that d(u2 ), d(v2 ), d(w2 ) = 2, 3 or a + b and a + b ≥ 4. We consider the following cases without loss of generality: • If d(u2 ) = d(v2 ) = d(w2 ) = 2, then a = 3/(a + b − 1) < 2, a contradiction. • If d(u2 ) = d(v2 ) = 2, d(w2 ) = 3, then a = 4/(a + b − 1) < 2, a contradiction. • If d(u2 ) = d(v2 ) = 2, d(w2 ) = a + b, then a = 1 + 2/(a + b − 1) < 2, a contradiction. • If d(u2 ) = 2, d(v2 ) = d(w2 ) = 3, then a = 5/(a + b − 1) < 2, a contradiction. • If d(u2 ) = 2, d(v2 ) = 3, d(w2 ) = a + b, then m = 2 and a = 1 + 3/(a + b − 1). By Lemmas 2.2 and 2.5 (ii), we have a + b = 4 and a = 2. Hence d(wi ) = d(w2 ) = 4 for 2 ≤ i ≤ k − 1. By (1) and (2), S(wk−1 ) = 4 + 2 + d(wk ) = 10. Thus d(wk ) = 4. Similarly, S(v2 ) = 4 + d(r2 ) + d(tq−1 ) = 8. It implies that d(r2 ) = d(tq−1 ) = 2. Thus S(r2 ) = 6 = 3 + d(r3 ). Hence d(r3 ) = 3. On the other hand, d(r3 ) ∈ {2, 4} by Lemma 2.5 (ii) and the fact that d(wk ) = 4. This is a contradiction. • If d(u2 ) = 2, d(v2 ) = d(w2 ) = a + b, then a = 2 + 1/(a + b − 1) is not an integer, a contradiction. • If d(u2 ) = d(v2 ) = d(w2 ) = 3, then n = m = k = 2 and a = 6/(a + b − 1). It follows from Lemma 2.5 (iii) that a + b = 4 and a = b = 2. By (1) and (2), S(v2 ) = 4 + d(r2 ) + d(tq−1 ) = 8. It implies that d(r2 ) = d(tq−1 ) = 2. Hence S(r2 ) = 3 + d(r3 ) = 6. It follows that d(r3 ) = 3 and l = 3. Similarly, we have p = q = 3. Therefore G = H32 , see Figure 3. By (3), H32 is 2-walk (2, 2)-linear. • If d(u2 ) = d(v2 ) = 3, d(w2 ) = a + b, then n = m = 2 and a = 1 + 4/(a + b − 1). Thus a + b = 5 and a = 2 by Lemma 2.5 (iii). Hence d(w1 ) = d(w2 ) = a + b = 5. For the vertex v2 , S(v2 ) = 5 + d(r2 ) + d(tq−1 ) = 9. It implies that d(r2 ) = d(tq−1 ) = 2. Thus S(r2 ) = 3 + d(r3 ) = 7, which is impossible since d(r3 ) ∈ {2, 3, 5} by Lemma 2.5 (ii).

1814

X. Fan, Y. Luo, X. Gao

• If d(u2 ) = 3, d(v2 ) = d(w2 ) = a + b, then a = 2 + 2/(a + b − 1) is not an integer, a contradiction. • If d(u2 ) = d(v2 ) = d(w2 ) = a+b, then n = m = k = 2 and a = 3. We claim that p = l = 2. Otherwise, let p, l > 2. By (1), S(w1 ) = a + b − 3 + 3(a + b), S(w2 ) = a + b − 3 + a + b + d(s2 ) + d(rl−1 ). Note that d(s2 ), d(rl−1 ) = 2 by assumption. We have S(w1 ) > S(w2 ). On the other hand, S(w1 ) = S(w2 ) by (2), a contradiction. Hence p = l = 2. Similarly, we have q = 2. Thus G ∈ G8 , see Figure 4, where b ≥ 1. It is easy to see that any graph G ∈ G8 is 2-walk (3, b)-linear. The following theorem follows directly from Lemmas 3.3–3.10.

Theorem 3.11. Let G be a graph and G0 be the graph obtained by deleting all pendant vertices in G. The graphs Hi for i = 1, . . . , 32 and those in Gj for j = 1, . . . , 9 are all connected tricyclic graphs G with δ(G0 ) ≥ 2 and exactly two main eigenvalues.

4.

Conclusion

In Section 3, we determined all connected tricyclic graphs with δ(G0 ) ≥ 2 and exactly two main eigenvalues. In fact, there exist tricyclic graphs with exactly two main eigenvalues and δ(G0 ) = 1. Figure 5 gives two examples. To determine all tricyclic graph with δ(G0 ) = 1 and exactly two main eigenvalues is still an open problem. Further studies could concentrate on investigating these graphs.

Figure 5.

Tricyclic graphs with exactly two main eigenvalues and δ(G0 ) = 1.

Acknowledgements We thank the referees whose useful suggestions and two examples of tricyclic graphs with exactly two main eigenvalues resulted in improvement to this article. This research was partially supported by the National Natural Science Foundation of China (No. 10971086 and No. 11201201). First author is currently a visiting Ph.D. student at the Department of Combinatorics and Optimization in University of Waterloo from September 2010 to September 2012.

References

[1] Bondy J.A., Murty U.S.R., Graph Theory with Applications, Elsevier, New York, 1976 [2] Cvetković D., Rowlinson P., Simić S., Eigenspaces of Graphs, Encyclopedia Math. Appl., 66, Cambridge University Press, Cambridge, 1997

1815

Tricyclic graphs with exactly two main eigenvalues

[3] Geng X., Li S., The spectral radius of tricyclic graphs with n vertices and k pendant vertices, Linear Algebra Appl., 2008, 428(11-12), 2639–2653 [4] Hagos E.M., Some results on graph spectra, Linear Algebra Appl., 2002, 356(1-3), 103–111 [5] Hou Y., Tian F., Unicyclic graphs with exactly two main eigenvalues, Appl. Math. Lett., 2006, 19(11), 1143–1147 [6] Hou Y.P., Zhou H.Q., Trees with exactly two main eigenvalues, J. Nat. Sci. Hunan Norm. Univ., 2005, 28(2), 1–3 (in Chinese) [7] Hu Z., Li S., Zhu C., Bicyclic graphs with exactly two main eigenvalues, Linear Algebra Appl., 2009, 431(10), 1848–1857 [8] Shi L., On graphs with given main eigenvalues, Appl. Math. Lett., 2009, 22(12), 1870–1874

1816