In 2010, Koolen and Park [4] gave a lower bound on the second largest eigenvalue of a distance-regular graph with diameter 3 in terms of valency k and intersection numbers a₁ and a₃.

Theorem 1.1. (cf. [4, Lemma 6]) Let Γ be a distance-regular graph with valency k and diameter 3. Then the second largest eigenvalue r of Γ satisfies

where λ=a1.

In 2011, Koolen, Park and Yu [6] generalized this theorem to the class of distance-regular graphs with diameter at least 4. We note that in [6, Theorem 3.1], they assumed that the valency k is at least three, but it is also true for k=2.

Theorem 1.2. (cf. [6, Theorem 3.1]) Let Γ be a distance-regular graph with valency k, diameter D ≥4. Then the second largest eigenvalue r of Γ satisfies

where λ=a1.

The proof of Theorem 1.2 also works for edge-regular graphs with diameter D ≥ 4. And for edge-regular graphs Γ with diameter 3, the proof of Theorem 1.1 works if we replace a₃ by a¯3(x)=1|Γ3(x)|∑ y∈ Γ 3 (x) a3(x,y), where x is a vertex of Γ.

In this paper, we will try to give a lower bound on the second largest eigenvalue r of an edge-regular graph with parameters (v,k,λ) in terms of λ. In order to do so, we will compare λ+λ2+4k2 with the local valency λ for edge-regular graphs with diameter D≥4. Since a lower bound on λ+λ2+4k2 does not give an immediate lower bound on the second largest eigenvalue of an edge-regular graph with diameter 3, we will consider the number λ−μ¯+(λ−μ¯)2+4(k−μ¯)2, where μ¯=k(k−1−λ)v−k−1. Once we have a relationship between r and λ for edge-regular graphs with diameter D≥3, we apply it to the class of distance-regular graphs with diameter D≥3. Then we obtain that for a distance-regular graph with diameter D≥4, the second largest eigenvalue is at least λ+2. For a distance-regular graph with diameter 3, we can show that the second largest eigenvalue is larger than λ+1 if the number v of vertices is large compared to λ k.

All the graphs considered in this paper are finite, undirected and simple. The reader is referred to [1] for more information. Let Γ be a connected graph with vertex set V(Γ). The distance dΓ(x,y) between two vertices x,y∈V(Γ) is the length of a shortest path between x and y in Γ. The diameter D=D(Γ) of Γ is the maximum distance between any two vertices of Γ. For each x∈V(Γ), let Γi(x) be the set of vertices of Γ at distance i from x (0≤i≤D). In addition, define Γ−1(x)=∅ and ΓD+1(x)=∅. For the sake of simplicity, let Γ(x)=Γ1(x) and we denote x~y if two vertices x and y are adjacent. In particular, Γ is regular with valency k if k=|Γ(x)| holds for all x∈ V(Γ). The graph Γ is called edge-regular with parameters (v,k,λ) if it has v vertices, is regular with valency k and satisfies that any two adjacent vertices of Γ have λ commnon neighbors. Note that for any vertex x of an edge-regular graph with parameters (v,k,λ), the subgraph induced on Γ(x) is a regular graph with valency λ.

For a connected graph Γ with diameter D, we choose two vertices x,y at distance i=dΓ(x,y), and consider the numbers ci(x,y)=|Γi−1(x)∩Γ(y)|, ai(x,y)=|Γi(x)∩Γ(y)| and bi(x,y)=|Γi+1(x)∩Γ(y)| (0≤i≤D). We say that the intersection number c_i (a_i and b_i, respectively) exists if the number c_i(x,y) (ai(x,y) and bi(x,y), respectively) does depend only on i=dΓ(x,y) not on the choice of x and y with dΓ(x,y)=i. Set c0=bD=0 and observe a₀=0 and c₁=1. A connected graph Γ with diameter D is called a distance-regular graph if there exist intersection numbers c_i, a_i, b_i for all i=0,1,…,D. Note that a distance-regular graph is edge-regular with parameters (v,b0,a1).

For any connected graph Γ with diameter D, the distance-i graph Γ_i (0≤i≤D) is the graph whose vertices are those of Γ and edges are the 2-subsets of vertices at mutual distance i in Γ. In particular, Γ1=Γ. An antipodal graph is a connected graph Γ with diameter D>1 for which its distance-D graph Γ_D is a disjoint union of complete graphs. A graph Γ is called bipartite if it has no odd cycle. (If Γ is a distance-regular graph with diameter D and bipartite, then a1=a2=…=aD=0.)

For a connected graph Γ with diameter D, the adjacency matrix A=A(Γ) is the matrix whose rows and columns are indexed by V(Γ), where the (x, y)-entry is 1 whenever x≃ y and 0 otherwise. The eigenvalues of Γ are the eigenvalues of A(Γ). For a partition Π={P1,P2,…,Pl} of the vertex set V(Γ), we look at the numbers β_ij (1≤i,j,≤l), where vertices in P_i have averagely β_ij neighbors in P_j. Then the quotient matrix Q=Q(Π) corresponding to the partition Π is the ℓ △ ℓ matrix whose (i,j)-entry is β_ij. Note that the eigenvalues of the quotient matrix Q interlace the eigenvalues of Γ (see [2, Corollary 2.5.4]).

Recall that the same proof of Theorem 1.2 also works for any edge-regular graph Γ with parameters (v,k,λ) and diameter D≥4, and hence the second largest eigenvalue r of Γ is at least λ+λ2+4k2.

In this section, for an edge-regular graph Γ with parameters (v,k,λ), second largest eigenvalue r and diameter D≥4, we compare λ+λ2+4k2 with the local valency λ to find a relationship between r and λ. Note that if k=2, then Γ is an n-gon for n≥8 and r>λ+1.

Lemma 3.1. Let Γ be an edge-regular graph with parameters (v,k,λ). Then for any positive integer t, λ+λ2+4k2>λ+t if and only if λ<1tk−t.

Proof. Let t be a positive integer. Clearly, λ+λ2+4k2>λ+t is equivalent to λ2+4k>λ+2t. Since λ+2t>0, we know that λ2+4k>λ+2t is equivalent to λ2+4k>(λ+2t)2=λ2+4tλ+4t2. As λ2+4k>λ2+4tλ+4t2 is equivalent to tλ<k−t2, we conclude that λ+λ2+4k2>λ+t if and only if λ<1tk−t. This finishes the proof.

Remark 3.2. (i) As λ≥0, the condition λ<kt−t is meaningful when k>t2.

(ii) For t=1, we have that λ+λ2+4k2>λ+1 if and only if λ<k−1. And λ<k−1 is true except when the graph is a complete graph. (It also can be obtained from an easy calculation, λ+λ2+4k2=λ+λ2+4(λ+1+b1)2=λ+(λ+2)2+4b12≥λ+1 with equality holds if and only if b₁=0, where b1=k−λ−1.)

(iii) For t=2, we have that λ+λ2+4k2>λ+2 if and only if λ<12k−2 (and k>4). In Theorem 3.4, we will also consider the case λ≥12k−2 for distance-regular graphs with diameter D≥4.

We combine Theorem 1.2 and Lemma 3.1, and then we obtain the following result.

Theorem 3.3. Let Γ be an edge-regular graph with parameters (v,k,λ), second largest eigenvalue r and diameter D≥4. For any positive integer t, if λ<1tk−t, then r>λ+t.

Proof. Since D≥4, Theorem 1.2 implies that r≥λ+λ2+4k2. Assume that λ<1tk−t, then Lemma 3.1 says that λ+λ2+4k2>λ+t. Thus, we obtain that r>λ+t. This finishes the proof.

We apply this result to the class of distance-regular graphs with diameter D≥4. Then we obtaind the following result.

Theorem 3.4. Let Γ be a distance-regular graph with valency k≥2, intersection number a₁=λ, second largest eigenvalue r and diameter D≥4. Then r≥λ+2.

Proof. If k=2, then Γ is an n-gon for n≥8 and r≥2=λ+2 (as λ=0). So, we may assume that k ≥ 3.

If λ≥12k−1, then by [5, Theorem 16], we know that Γ is the flag graph of a regular generalized D-gon of order (s,s) for some s≥2, and the second largest eigenvalue r of Γ satisfies r≥λ+2s≥λ+2 (see, [1, Section 6.5] or [3]).

If 12k−2≤λ<12k−1, then Γ satisfies either (k is even and λ=12k−2) or (k is odd and λ=12k−32). The first case implies that r≥λ+2 as λ+λ2+4k2≥λ+2. And the second case implies that r>λ+3 as λ+λ2+4k2>λ+3.

If λ<12k−2, then by Theorem 3.3, we know that r>λ+2. This finishes the proof.

Remark 3.5. (i) In Theorem 3.4, r=λ+2 holds only for the 8-gon.

(ii) The flag graph of a regular generalized 4-gon of order (2,2) has second largest eigenvalue r=3=1+2=λ+2. And some antipodal distance-regular graphs with diameter 4 satisfy that k is even, λ=12k−2 and r=λ+λ2+4k2=λ+2 (see, [1, p.421]).

Recall that for an edge-regular graph Γ with parameters (v,k,λ) and diameter 3, if we replace a₃ by a¯3(x) and follow the proof of Theorem 1.1, then we obtain that the second largest eigenvalue of Γ is at least min{λ+λ2+4k2,a¯3(x)}, where x is a vertex of Γ and a¯3(x)=1|Γ3(x)|∑ y∈ Γ 3 (x) a3(x,y). If a¯3(x)≥λ+λ2+4k2, then we find a result similar to Lemma3.3. But it is not true in general for edge-regular graphs with diameter 3.

In this section, for an edge-regular graph Γ with parameters (v,k,λ), second largest eigenvalue r and diameter 3, we compare λ−μ¯+(λ−μ¯)2+4(k−μ¯)2 with the local valency λ to find a relationship between r and λ. Note that if k=2, then Γ is an n-gon for n∈{6,7} and r≥λ+1.

Lemma 4.1. Let Γ be an edge-regular graph with parameters (v,k,λ), second largest eigenvalue r and diameter 3. Then r≥λ−μ¯+(λ−μ¯)2+4(k−μ¯)2, where μ¯=k(k−1−λ)v−k−1.

Proof. Let x be a vertex of Γ. Consider a partition P={{x},Γ1(x),Γ2(x)∪Γ3(x)} of the set of vertices of Γ. As there are v-k-1 vertices in Γ2(x)∪Γ3(x), we know that vertices in Γ2(x)∪Γ3(x) have averagely μ¯=k(k−1−λ)v−k−1 neighbors in Γ(x). Then one can easily see that the following matrix Q is the quotient matrix corresponding to the partition P :

Note that the matrix Q has eigenvalues

Thus, we know that the second largest eigenvalue r of Γ is at least the second largest eigenvalue of Q (see for example [2, Corollary 2.5.4]). This finishes the proof.

In [6, Proposition 3.2], it was shown that for a distance-regular graph with second largest eigenvalue r, intersection numbers a1=λ, c2=μand diameter 3, r>λ+1−μ holds. We generalize this to the class of edge-regular graphs (with diameter 3).

Lemma 4.2. Let Γ be an edge-regular graph with parameters (v,k,λ), second largest eigenvalue r and diameter 3. Then r>λ+1−μ¯, where μ¯=k(k−1−λ)v−k−1.

Proof. Note that r>0 (see for example Lemma 3.3). If λ−μ¯<−2, then λ+1−μ¯<−1<r holds. So, we may assume that λ−μ¯≥−2.

Since k>λ+1, we have k−μ¯>λ+1−μ¯, and this implies that (λ−μ¯)2+4(k−μ¯)>(λ−μ¯)2+4(λ+1−μ¯)=(λ+2−μ¯)2. As λ+2−μ¯≥0, we obtain that (λ−μ¯)2+4(k−μ¯)>λ+2−μ¯, and hence λ−μ¯+(λ−μ¯ )2+4(k−μ¯)2>λ+1−μ¯ holds. Thus, by Lemma 4.1, we know that r>λ+1−μ¯. This finishes the proof.

Remark 4.3. (i) Lemma 4.2 is also true for edge-regular graphs with diameter at least 4. But we have a better bound for edge-regular graphs with diameter at least 4. (see for example Lemma 3.3)

(ii) For distance-regular graphs with diameter 3, c2=k(k−1−λ)k2>k(k−1−λ)k2+k3=μ¯ holds. Thus, Lemma 4.2 slightly strengthens a result of [6, Proposition 3.2].

Lemma 4.4. Let Γ be an edge-regular graph with parameters (v,k,λ) and diameter 3. Let s be an integer satisfying k>sλ+s2. If v>(λ+1+s)k−λ−1k−sλ−s2k+k+1, then λ−μ¯+(λ−μ¯)2+4(k−μ¯)2>λ+s, where μ¯=k(k−1−λ)v−k−1.

Proof. From the assumption v>(λ+1+s)k−λ−1k−sλ−s2k+k+1, we have that v−k−1>(λ+1+s)k−λ−1k−sλ−s2k. Since v−k−1>0 and k−sλ−s2>0, we obtain that k−sλ−s2>(λ+1+s)k(k−λ−1)v−k−1=(λ+1+s)μ¯.

Multiply by 4 and then we obtain that 4k−4sλ−4s2>4λμ¯+4μ¯+4sμ¯.

Add λ2+μ¯2 to both sides. Then we have that λ2+μ¯2+4k−4sλ−4s2>λ2+μ¯2+4λμ¯+4μ¯+4sμ¯, i.e., (λ−μ¯)2+4(k−μ¯)>(λ+μ¯)2+4s(λ+μ¯)+(2s)2=(λ+μ¯+2s)2 holds. Since (λ−μ¯)2+4(k−μ¯)>(λ+μ¯+2s)2=|λ+μ¯+2s|≥λ+μ¯+2s, we obtain that λ−μ¯+(λ−μ¯)2+4(k−μ¯)2>λ+s. This finishes the proof.

In the following theorem, we consider the case s=1. And we find that the second largest eigenvalue of an edge-regular graph with parameters (v,k,λ) and diameter 3 is larger than λ+1 when v is large compared to λk.

Theorem 4.5. Let Γ be an edge-regular graph with parameters (v,k,λ), second largest eigenvalue r and diameter 3. If v>(λ+3)k+1, then r>λ+1.

Proof. Note that k>λ+1 holds (as the diameter of Γ is 3). Set s=1 in Lemma 4.4. Then Lemma4.4 says that v>(λ+3)k+1 implies that λ−μ¯+(λ−μ¯)2+4(k−μ¯)2>λ+1. By Lemma 4.1, we obtain that r≥λ−μ¯+(λ−μ¯)2+4(k−μ¯)2>λ+1. This finishes the proof.

We apply this result to the class of distance-regular graphs with intersection number a1=λ=0 and diameter 3. Then we obtaind the following result.

Theorem 4.6. Let Γ be a distance-regular graph with valency k≥2, intersection number a1=λ=0, second largest eigenvalue r and diameter 3. Then r≥λ+1.

Proof. If the graph Γ has more than 3k+1 vertices, then by Theorem 4.5, we know that r>λ+1. So, we assume that Γ has at most 3k+1 vertices. Then by [7, Theorem 1], we know that Γ is either a 7-gon, a Taylor graph or a bipartite graph. Note that a 7-gon satisfies r>1=λ+1 and that a Taylor graph with λ=0 satisfies r=1=λ+1. So, we may assume that Γ is bipartite. Then Γ satisfies that r≥k−c2≥1=λ+1, and r=1 if and only if Γ is a Taylor graph. This finishes the proof.

Remark 4.7. In Theorem 4.6, r=λ+1 with λ=0 holds only for a Taylor graph, for example, the 6-gon and the 3-cube.