betaFeedback

WorksMathematics

2-Walk-regular graphs with k2k_2 at most twice the valency

Abstract

In this paper, we characterize 22-walk-regular graphs with valency kk, diameter at least four and k2≤2kk_2\leq 2k, generalizing a result of Koolen and Park, and classify the distance-regular graphs satisfying these conditions. We also classify 22-walk-regular graphs with valency kk, diameter at least four and at most 4k+44k+4 vertices.

Introduction

A graph is 2-walk-regular if, for every nonnegative integer ℓ\ell, the number of walks of length ℓ\ell between vertices at distance at most two depends only on their distance. Such graphs are generalizations of distance-regular graphs. In this paper, we study 2-walk-regular graphs with valency k≥3k \ge3, diameter D≥4D \ge4 and k2≤2kk_2 \le2k.

We first show that such graphs are bipartite if c2≥2c_2 \ge2.

Theorem 1.1. Let Γ\Gamma be a 2-walk-regular graph with valency k≥3k \ge3 and diameter D≥4D \ge4. If k2≤2kk_2 \le2k and c2≥2c_2 \ge2, then Γ\Gamma is bipartite.

Remark. (i) Koolen and Park [10 Theorem 17] showed that for ε>0\varepsilon> 0, there exists a real number κ(ε)\kappa(\varepsilon) such that a distance-regular graph with valency k≥κ(ε)k \ge\kappa(\varepsilon), diameter D≥3D \ge3 and k2≤(2−ε)kk_2 \le(2-\varepsilon)k is either a Taylor graph or a bipartite graph with diameter 3.

(ii) The Hamming graph H(3,3)H(3,3) (D=3D = 3, c2=2c_2 = 2), the line graph of the Petersen graph (D=3D = 3, c2=1c_2 = 1), and the Coxeter graph (D=4D = 4, c2=1c_2 = 1) are nonbipartite distance-regular graphs with k2=2kk_2 = 2k.

As an application of Theorem 1.1, we obtain the following characterization of 2-walk-regular graphs with valency k≥3k \ge3, diameter D≥4D \ge4 and k2≤2kk_2 \le2k.

Theorem 1.2. Let Γ\Gamma be a 2-walk-regular graph with valency k≥3k \ge3 and diameter D≥4D \ge4. Then k2≤2kk_2 \le2k if and only if Γ\Gamma is one of the following graphs:

(i) a Hadamard graph, with k≥4k \ge4 even, D=4D = 4, and c2=k/2c_2 = k/2;

(ii) the 5-cube, with k=5k = 5, D=5D = 5, and c2=2c_2 = 2;

(iii) the incidence graph of a GDDDP(2,k+1;k;0,k−12)(2,k+1;k;0,\frac{k-1}{2}), with k≥5k \ge5 odd, D=4D=4, and c2=k−12c_2=\frac{k-1}{2};

(iv) a cubic 1-walk-regular graph with diameter at least four and girth at least five; here k=3k=3 and c2=1c_2=1;

(v) a line graph L(H)L(H), where HH is a cubic 3-walk-regular graph with diameter at least four and girth at least six; here k=4k=4 and a1=c2=1a_1=c_2=1.

Remark. (i) Qiao, Park and Koolen [13 Theorem 1.3] classified 2-walk-regular graphs with valency k≥3k \ge3, diameter D≥4D \ge4 and c2>13kc_2 > \frac{1}{3}k.

(ii) Conder and Nedela [4 Proposition 2.5] constructed infinitely many finite cubic 3-arctransitive graphs HH with girth at least 10. For each such graph HH, the graphs HH and L(H)L(H) belong to (iv) and (v) respectively. And Lemma 4.3 implies that the graphs L(H)L(H) are pairwise nonisomorphic. Hence both (iv) and (v) contain infinitely many graphs.

Then we classify distance-regular graphs with valency kk, diameter D≥4D \ge4 and k2≤2kk_2 \le2k.

Theorem 1.3. Let Γ\Gamma be a distance-regular graph with valency k≥3k \ge3 and diameter D≥4D \ge4. Then k2≤2kk_2 \le2k if and only if Γ\Gamma is a Hadamard graph or one of the eleven graphs in Table 1.

GraphkkvvDDIntersection array
Pappus3184{3,2,2,1;1,1,2,3}\{3,2,2,1;1,1,2,3\}
Coxeter3284{3,2,2,1;1,1,1,2}\{3,2,2,1;1,1,1,2\}
Tutte 8-cage3304{3,2,2,2;1,1,1,3}\{3,2,2,2;1,1,1,3\}
Dodecahedron3205{3,2,1,1,1;1,1,1,2,3}\{3,2,1,1,1;1,1,1,2,3\}
Desargues3205{3,2,2,1,1;1,1,2,2,3}\{3,2,2,1,1;1,1,2,2,3\}
Tutte 12-cage31266{3,2,2,2,2,2;1,1,1,1,1,3}\{3,2,2,2,2,2;1,1,1,1,1,3\}
Biggs–Smith31027{3,2,2,2,1,1,1;1,1,1,1,1,1,3}\{3,2,2,2,1,1,1;1,1,1,1,1,1,3\}
Foster3908{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}\{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3\}
GO(2,1)GO(2,1)4454{4,2,2,2;1,1,1,2}\{4,2,2,2;1,1,1,2\}
GD(2,1)GD(2,1)41896{4,2,2,2,2,2;1,1,1,1,1,2}\{4,2,2,2,2,2;1,1,1,1,1,2\}
5-cube5325{5,4,3,2,1;1,2,3,4,5}\{5,4,3,2,1;1,2,3,4,5\}

Table 1. Non-Hadamard distance-regular graphs with k≥3k \ge3, D≥4D \ge4, and k2=2kk_2=2k

Remark. (i) Koolen and Park [10 Theorem 20] classified distance-regular graphs with valency kk, diameter D≥3D \ge3 and k2≤32kk_2 \le\frac{3}{2}k.

(ii) The graphs GO(2,1)GO(2,1) and GD(2,1)GD(2,1) are the line graphs of the Tutte 8-cage and Tutte 12-cage, respectively. And for k=4k=4, the 4-cube is a Hadamard graph, and hence is not included in Table 1.

Then we classify 2-walk-regular graphs with valency kk, diameter D≥4D \ge4 and v≤4k+4v \le4k+4 vertices.

Theorem 1.4. Let Γ\Gamma be a 2-walk-regular graph with valency k≥3k \ge3, diameter D≥4D \ge4, and vv vertices. Then v≤4k+4v \le4k+4 if and only if Γ\Gamma is one of the following graphs:

(i) a Hadamard graph with kk even and v=4kv=4k;

(ii) the incidence graph of a GDDDP(2,k+1;k;0,k−12)(2,k+1;k;0,\frac{k-1}{2}) with kk odd and v=4k+4v=4k+4.

Remark. Qiao, Koolen and Park [12 Theorem 1.2] gave a characterization of 2-walk-regular graphs with valency kk, diameter D≥3D \ge3 and v≤αkv \le\alpha k vertices for a fixed α>2\alpha> 2. They also showed that a 2-walk-regular graph Γ\Gamma with valency kk, diameter D≥3D \ge3 and vv vertices is distance-regular if v≤3k+1v \le3k + 1, or v≤4k+1v \le4k + 1 and Γ\Gamma is bipartite (see [12 Corollary 4.2]). They also gave an infinite family of the incidence graphs of GDDDP(2,k+1;k;0,k−12)(2, k + 1; k; 0, \frac{k-1}{2}). Such graphs were also studied by Jin, Koolen and Lv [8].

This paper is organized as follows: In § 2, we give some definitions and preliminary results. In § 3, we give a proof of Theorem 1.1. In § 4, we determine feasible parameters (k,a1)(k, a_1) for 2-walk-regular graphs with k2≤2kk_2 \le2k and c2=1c_2 = 1 (Lemma 4.1), and characterize the corresponding 2-walk-regular graphs with valency four (Lemma 4.3). Then we give proofs of Theorems 1.2 and 1.3. In § 5, we determine 2-walk-regular graphs with v≤4k+4v \le4k + 4 and c2=1c_2 = 1 (Lemma 5.2). Then we give a proof of Theorem 1.4.

Definitions and preliminaries

All graphs considered in this paper are finite, undirected and simple. The reader is referred to [1, 7] for more information.

Let Γ=(V(Γ),E(Γ))\Gamma= (V(\Gamma), E(\Gamma)) be a connected graph. Two vertices x,yx, y are adjacent if {x,y}\{x,y\} is in E(Γ)E(\Gamma), denoted by x∼yx \sim y. The distance d(x,y)=dΓ(x,y)d(x,y) = d_\Gamma(x,y) between two vertices x,y∈V(Γ)x,y \in V(\Gamma) is the length of a shortest path between xx and yy in Γ\Gamma. The diameter D=DΓD = D_\Gamma is the maximum distance between any two vertices in Γ\Gamma. For each x∈V(Γ)x \in V(\Gamma), let Γi(x)\Gamma_i(x) be the set of vertices at distance ii from xx (0≤i≤D0 \le i \le D). In addition, we define Γ−1(x)=ΓD+1(x)=∅\Gamma_{-1}(x) = \Gamma_{D+1}(x) = \varnothing. For simplicity, we write Γ(x)=Γ1(x)\Gamma(x) = \Gamma_1(x). For x∈V(Γ)x \in V(\Gamma), the valency of xx in Γ\Gamma is ∣Γ(x)∣|\Gamma(x)|. A graph is regular with valency kk if ∣Γ(x)∣=k|\Gamma(x)| = k for all x∈V(Γ)x \in V(\Gamma). The local graph Δx\Delta_x of Γ\Gamma at xx is the subgraph induced on Γ(x)\Gamma(x). For two vertices x,yx,y at distance two, the μ\mu-graph MxyM_{xy} is the subgraph induced on Γ(x)∩Γ(y)\Gamma(x) \cap\Gamma(y).

Let Γ\Gamma be a graph with diameter DD and let x,yx,y be vertices of Γ\Gamma at distance ii ($0 \le i \le D$). Let ci(x,y)=∣Γi−1(x)∩Γ(y)∣c_i(x,y) = |\Gamma_{i-1}(x) \cap\Gamma(y)|, ai(x,y)=∣Γi(x)∩Γ(y)∣a_i(x,y) = |\Gamma_i(x) \cap\Gamma(y)|, bi(x,y)=∣Γi+1(x)∩Γ(y)∣b_i(x,y) = |\Gamma_{i+1}(x) \cap\Gamma(y)|, ki(x)=∣Γi(x)∣k_i(x) = |\Gamma_i(x)|. The intersection numbers ci(x,y)c_i(x,y), ai(x,y)a_i(x,y), bi(x,y)b_i(x,y) are called well-defined if the numbers do not depend on the choice of xx and yy but only on ii. A graph Γ\Gamma with diameter DD is called tt-partially distance-regular if these numbers ci(x,y)c_i(x,y), ai(x,y)a_i(x,y) and bi(x,y)b_i(x,y) are well-defined for 0≤i≤t0 \le i \le t (where it is implicitly assumed that t≤Dt \le D). If this is the case, then these numbers are denoted simply by cic_i, aia_i and bib_i (0≤i≤t0 \le i \le t). The relation ki−1(x)bi−1=ki(x)cik_{i-1}(x)b_{i-1} = k_i(x)c_i shows that ki=ki(x)k_i = k_i(x) (0≤i≤t0 \le i \le t) are also well-defined. If t=Dt = D, then the graph Γ\Gamma is called a distance-regular graph, and the array {b0=k,b1,…,bD−1;c1=1,c2,…,cD}\{b_0 = k, b_1, \ldots, b_{D-1}; c_1 = 1, c_2, \ldots, c_D\} is called the intersection array of $\Gamma. A distance-regular graph with intersection array {2μ,2μ−1,μ,1;1,1,2μ−1,2μ}\{2\mu, 2\mu- 1, \mu, 1; 1, 1, 2\mu- 1, 2\mu\} is called a Hadamard graph.

A graph Γ\Gamma is called tt-walk-regular if the number of walks of every given length ℓ\ell between two vertices x,y∈V(Γ)x,y \in V(\Gamma) depends only on the distance between xx and yy, provided that d(x,y)≤td(x,y) \le t (where it is implicitly assumed that the diameter of Γ\Gamma is at least tt). A tt-walk-regular graph is a tt-partially distance-regular graph (see [5 Proposition 3.15]).

The distance-ii matrix AiA_i of Γ\Gamma is the matrix whose rows and columns are indexed by the vertices of Γ\Gamma and the (x,y)(x,y)-entry is 1 whenever d(x,y)=id(x,y) = i and 0 otherwise. The adjacency matrix of Γ\Gamma is A1A_1, and it is simply denoted by AΓA_\Gamma or AA. The eigenvalues of Γ\Gamma are the eigenvalues of its adjacency matrix AA. We denote the transpose of a matrix AA by ATA^T.

Let Γ\Gamma be a tt-walk-regular graph with vv vertices, and let θ\theta be an eigenvalue of Γ\Gamma with multiplicity m(θ)m(\theta). The matrix EE corresponding to the orthogonal projection onto the eigenspace associated to θ\theta is called the minimal idempotent associated to θ\theta. The map

ρ:V(Γ)→Rv,x↦x^=vm(θ)Eex\rho: V(\Gamma) \to\mathbb{R}^v,\qquad x \mapsto\widehat{x} = \sqrt{\frac{v}{m(\theta)}} E e_x

is called the normalized representation associated to θ\theta. Note that there exist constants αi\alpha_i such that Ai∘E=αiAiA_i \circ E = \alpha_i A_i (0≤i≤t0 \le i \le t), where ∘\circ is the entrywise product (see [6 Theorem 3.1]), i.e., the (x,y)(x,y)-entry of EE only depends on the distance between xx and yy if d(x,y)=i≤td(x,y)=i \le t. Then α0=m(θ)/v\alpha_0=m(\theta)/v, ∥x∥2=1\lVert x\rVert^2=1, and ui(θ):=αiα0=⟨x^,y^⟩u_i(\theta):=\frac{\alpha_i}{\alpha_0}=\langle\hat{x},\hat{y}\rangle (0≤i≤t0\le i\le t) is well-defined, where x,yx,y are any two vertices of Γ\Gamma at distance ii. As AE=θEAE=\theta E, we have θx^=∑y∈Γ(x)y^\theta\hat{x}=\sum_{y\in\Gamma(x)}\hat{y} and

ciui−1(θ)+aiui(θ)+biui+1(θ)=θui(θ)(1≤i≤t−1).(1)c_i u_{i-1}(\theta)+a_i u_i(\theta)+b_i u_{i+1}(\theta)=\theta u_i(\theta)\qquad(1\le i\le t-1). \tag*{(1)}

The sequence (u0(θ),u1(θ),…,ut(θ))(u_0(\theta),u_1(\theta),\ldots,u_t(\theta)) is called the tt-partial standard sequence of Γ\Gamma corresponding to the eigenvalue θ\theta. For a distance-regular graph with diameter DD, the standard sequence is the DD-partial standard sequence (see [1 p. 128]). Note that for a 22-walk-regular graph, by (1), we have

u0(θ)=1,u1(θ)=θk,u2(θ)=θ2−a1θ−kkb1.(2)u_0(\theta)=1,\qquad u_1(\theta)=\frac{\theta}{k},\qquad u_2(\theta)=\frac{\theta^2-a_1\theta-k}{kb_1}. \tag*{(2)}

A partition Π={B1,B2,…,Bn}\Pi=\{B_1,B_2,\ldots,B_n\} of V(Γ)V(\Gamma) is equitable if there exist non-negative integers qijq_{ij} (1≤i,j≤n1\le i,j\le n) such that every vertex in BiB_i has exactly qijq_{ij} neighbors in BjB_j. When Π\Pi is equitable, the distribution diagram of Γ\Gamma with respect to Π\Pi is a diagram in which each block BiB_i is represented by a balloon. We draw a line from the balloon representing BiB_i to that of BjB_j if qij>0q_{ij}>0, placing the number qijq_{ij} above the line near BiB_i. Inside the balloon we write ∣Bi∣\lvert B_i\rvert, and below it we write qiiq_{ii}. If qii=0q_{ii}=0, we write −- instead of 00.

An incidence structure I=(P,B,I)\mathcal{I}=(\mathcal{P},\mathcal{B},I) consists of a set P\mathcal{P} of points, a set B\mathcal{B} of blocks (disjoint from P\mathcal{P}), and a relation I⊆P×BI\subseteq\mathcal{P}\times\mathcal{B} called incidence. If (p,B)∈I(p,B)\in I, then we say that the point pp and the block BB are incident. We regard each block BB as a subset of P\mathcal{P}. Given an incidence structure I=(P,B,I)\mathcal{I}=(\mathcal{P},\mathcal{B},I), its dual incidence structure is defined as I∗=(B,P,I∗)\mathcal{I}^*=(\mathcal{B},\mathcal{P},I^*), where I∗={(B,p)∣(p,B)∈I}I^*=\{(B,p)\mid(p,B)\in I\}. The point-block incidence graph Γ(I)\Gamma(\mathcal{I}) of I\mathcal{I} is the graph with vertex set P∪B\mathcal{P}\cup\mathcal{B}, where two vertices are adjacent if and only if they are incident. Note that the point-block incidence graph of an incidence structure is bipartite.

A group divisible design D\mathcal{D} with parameters (n,m;k;λ1,λ2)(n,m;k;\lambda_1,\lambda_2), denoted by GDD⁡(n,m;k;λ1,λ2)\operatorname{GDD}(n,m;k;\lambda_1,\lambda_2), is an ordered triple (P,G,B)(\mathcal{P},\mathcal{G},\mathcal{B}), where P\mathcal{P} is a set of points, G\mathcal{G} is a partition of P\mathcal{P} into mm subsets of size nn (called groups), and B\mathcal{B} is a collection of kk-subsets of P\mathcal{P} (called blocks), such that each pair of points from the same group appears in exactly λ1\lambda_1 blocks, and each pair of points from different groups appears in exactly λ2\lambda_2 blocks. The triple I=(P,B,I)\mathcal{I}=(\mathcal{P},\mathcal{B},I), with the natural incidence relation II, forms an incidence structure, and we consider its dual I∗=(B,P,I∗)\mathcal{I}^*=(\mathcal{B},\mathcal{P},I^*). If there exists a partition G′\mathcal{G}' of B\mathcal{B} such that the triple (B,G′,P)(\mathcal{B},\mathcal{G}',\mathcal{P}) is a GDD⁡(n,m;k;λ1,λ2)\operatorname{GDD}(n,m;k;\lambda_1,\lambda_2), then we say that D\mathcal{D} is a group divisible design with the dual property with parameters (n,m;k;λ1,λ2)(n,m;k;\lambda_1,\lambda_2), denoted by GDDDP⁡(n,m;k;λ1,λ2)\operatorname{GDDDP}(n,m;k;\lambda_1,\lambda_2).

For the convenience of the reader, we list the following known results.

Lemma 2.1 (cf. [1 Proposition 4.1.6]). Let Γ\Gamma be a tt-walk-regular graph with diameter D≥tD\ge t. If i,j≤ti,j\le t and i+j≤Di+j\le D, then bi≥cjb_i\ge c_j holds.

Lemma 2.2 (cf. [3 Proposition 5.1]). Let Γ\Gamma be a 22-walk-regular graph with diameter D≥3D\ge3 and distinct eigenvalues k=θ0>θ1>⋯>θdk=\theta_0>\theta_1>\cdots>\theta_d. Let Δ\Delta be a local graph of Γ\Gamma with smallest eigenvalue η\eta. Then

η≥−1−b1θ1+1.\eta\ge-1-\frac{b_1}{\theta_1+1}.

Lemma 2.3 (cf. [13 Lemma 2.5]). Let Γ\Gamma be a 22-walk-regular graph with diameter D≥3D\ge3 and distinct eigenvalues k=θ0>θ1>⋯>θdk=\theta_0>\theta_1>\cdots>\theta_d. If Γ\Gamma contains an induced quadrangle, then

θ1≤b1−1.\theta_1\le b_1-1.

Lemma 2.4 (cf. [13 Theorem 1.3]). Let Γ\Gamma be a 22-walk-regular graph with valency k≥3k\ge3 and diameter D≥4D\ge4. If c2>k/3c_2>k/3, then Γ\Gamma is a Hadamard graph, the 55-cube, or the incidence graph of a GDDDP⁡(2,m;k;0,c2)\operatorname{GDDDP}(2,m;k;0,c_2) for some integer mm.

Lemma 2.5 (cf. [11 Theorem 2]). Let k≥3k \ge3 be odd, and let DD be a GDDDP(2,k+1;k;0,k−12)(2,k+1;k;0,\frac{k-1}{2}) with incidence graph Γ\Gamma. Then Γ\Gamma is 2-walk-regular with v=4k+4v=4k+4 vertices. Moreover, for each vertex xx, there exists a unique vertex x′x' at distance four from xx, and the partition

Π(x)={{x},Γ(x),Γ2(x),Γ(x′),Γ3(x)∖Γ(x′),{x′}}\Pi(x)=\{\{x\},\Gamma(x),\Gamma_2(x),\Gamma(x'),\Gamma_3(x)\setminus\Gamma(x'),\{x'\}\}

is equitable with distribution diagram as in Figure 1.

Figure 1. Distribution diagram of the incidence graph of GDDDP(2,k+1;k;0,k−12)(2,k+1;k;0,\frac{k-1}{2})

Lemma 2.6 (cf. [3 Propositions 3.6 and 3.4]). Let Γ\Gamma be a graph with valency k≥3k \ge3, diameter D≥3D \ge3 and girth gg.

(i) If Γ\Gamma is 1-walk-regular and k=3k=3, then Γ\Gamma is 2-walk-regular.

(ii) If Γ\Gamma is 3-walk-regular and g≥6g \ge6, then L(Γ)L(\Gamma) is 2-walk-regular.

Lemma 2.7 (cf. [9 Lemma 6]). Let Γ\Gamma be a 2-walk-regular graph with valency k≥3k \ge3, diameter D≥4D \ge4, and distinct eigenvalues k=θ0>θ1>⋯>θdk=\theta_0>\theta_1>\cdots>\theta_d. Then

θ1≥a1+a12+4k2.\theta_1 \ge\frac{a_1+\sqrt{a_1^2+4k}}{2}.

Proof. Let x,y∈V(Γ)x,y\in V(\Gamma) with d(x,y)=4d(x,y)=4. Then the graph induced on {x}∪Γ(x)∪{y}∪Γ(y)\{x\}\cup\Gamma(x)\cup\{y\}\cup\Gamma(y) has largest eigenvalue a1+a12+4k2\frac{a_1+\sqrt{a_1^2+4k}}{2} with multiplicity 2. The result follows by interlacing.

Proof of Theorem 1.1

Proof of Theorem 1.1. Let Γ\Gamma be a 2-walk-regular graph with valency k≥3k \ge3, diameter D≥4D \ge4, satisfying k2≤2kk_2 \le2k and c2≥2c_2 \ge2.

Let τ>0\tau>0 and −σ<0-\sigma<0 be the roots of t2−a1t−kt^2-a_1t-k. Then

k=σ(a1+σ),τ=a1+σ,b1=(a1+σ+1)(σ−1),σ>1.(3)k=\sigma(a_1+\sigma),\qquad\tau=a_1+\sigma,\qquad b_1=(a_1+\sigma+1)(\sigma-1),\qquad\sigma>1. \tag*{(3)}

Let Δ\Delta be a local graph, and let μΔ\mu_\Delta be the average number of common neighbors in Δ\Delta over its unordered pairs of nonadjacent vertices, that is

μΔ=2kb1∑{y,z}⊆V(Δ)y≁z∣Δ(y)∩Δ(z)∣.\mu_\Delta=\frac{2}{kb_1}\sum_{\substack{\{y,z\}\subseteq V(\Delta)\\y\not\sim z}}|\Delta(y)\cap\Delta(z)|.

For any two vertices p,qp,q of Γ\Gamma at distance 2, let δpq\delta_{pq} be the average degree of the μ\mu-graph M=MpqM=M_{pq}, that is

δpq=1c2∑y∈V(M)∣M(y)∣.\delta_{pq}=\frac{1}{c_2}\sum_{y\in V(M)}|M(y)|.

Claim 1. We have θ1≥τ\theta_1\ge\tau, and the local graph Δ\Delta has smallest eigenvalue at least −σ-\sigma. Moreover,

μΔ≤a1σ+1,μΔ≤a1(a1−1)b1.(4)\mu_\Delta\le\frac{a_1}{\sigma+1},\qquad\mu_\Delta\le\frac{a_1(a_1-1)}{b_1}. \tag*{(4)}

:::

Proof of Claim 1. By Lemma 2.7, we have θ1≥τ\theta_1 \ge\tau. Thus Lemma 2.2 shows that the smallest eigenvalue of the local graph Δ\Delta is at least

−1−b1θ1+1≥−1−b1τ+1=−σ.-1-\frac{b_1}{\theta_1+1}\ge-1-\frac{b_1}{\tau+1}=-\sigma.

In the local graph Δ\Delta, there are kb1kb_1 ordered nonadjacent pairs of vertices and ka1(a1−1)ka_1(a_1-1) walks of length two with distinct endpoints, among which tr⁡(AΔ3)\operatorname{tr}(A_{\Delta}^{3}) have adjacent endpoints. Hence

kb1μΔ=ka1(a1−1)−tr⁡(AΔ3).(5)kb_1\mu_{\Delta}=ka_1(a_1-1)-\operatorname{tr}(A_{\Delta}^{3}). \tag*{(5)}

Since tr⁡(AΔ3)≥0\operatorname{tr}(A_{\Delta}^{3})\ge0, this shows the second inequality in (4). Let ρ=a1/(σ+1)\rho=a_1/(\sigma+1). Since the spectrum of AΔA_{\Delta} lies in [−σ,a1][-\sigma,a_1], the polynomial f(t)=(t+σ)(t−ρ)f(t)=(t+\sigma)(t-\rho) is nonnegative on the spectrum. Since a1a_1 is an eigenvalue of AΔA_{\Delta}, we have tr⁡f(AΔ)≥f(a1)\operatorname{tr}f(A_{\Delta})\ge f(a_1). Using tr⁡(AΔ)=0\operatorname{tr}(A_{\Delta})=0 and tr⁡(AΔ2)=ka1\operatorname{tr}(A_{\Delta}^{2})=ka_1, this gives

tr⁡(AΔ3)+(σ−2ρ)ka1+σρ2k≥(a1+σ)(a1−ρ)2=σρ2k.\operatorname{tr}(A_{\Delta}^{3})+(\sigma-2\rho)ka_1+\sigma\rho^{2}k\ge(a_1+\sigma)(a_1-\rho)^2=\sigma\rho^{2}k.

Hence tr⁡(AΔ3)≥ka1(2ρ−σ)\operatorname{tr}(A_{\Delta}^{3})\ge ka_1(2\rho-\sigma). Substituting this bound into (5), we obtain

μΔ≤a1(a1−1−2ρ+σ)b1=a1σ+1.\mu_{\Delta}\le\frac{a_1(a_1-1-2\rho+\sigma)}{b_1}=\frac{a_1}{\sigma+1}.

This shows the first inequality in (4).

Claim 2. Γ\Gamma contains an induced quadrangle, τ≤θ1≤b1−1\tau\le\theta_1\le b_1-1 and σ≥2\sigma\ge2.

Proof of Claim 2. Assume that Γ\Gamma contains no induced quadrangle. Then every μ\mu-graph of Γ\Gamma is a clique. Hence in the local graph Δ\Delta, two nonadjacent vertices have exactly c2−1c_2-1 common neighbors. Claim 1 gives

c2−1=μΔ≤a1σ+1.(6)c_2-1=\mu_{\Delta}\le\frac{a_1}{\sigma+1}. \tag*{(6)}

Together with b1≤2c2b_1\le2c_2 and (3), we have

(a1+σ+1)(σ2−1)=b1(σ+1)≤2c2(σ+1)≤2(a1+σ+1),(a_1+\sigma+1)(\sigma^2-1)=b_1(\sigma+1)\le2c_2(\sigma+1)\le2(a_1+\sigma+1),

and hence σ≤3<2\sigma\le\sqrt{3}<2. Moreover, (6) implies a1≥(c2−1)(σ+1)>2a_1\ge(c_2-1)(\sigma+1)>2, since c2≥2c_2\ge2 and σ>1\sigma>1. The local graph Δ\Delta is connected, since its nonadjacent vertices have c2−1>0c_2-1>0 common neighbors. By Claim 1, the smallest eigenvalue of Δ\Delta is at least −σ>−2-\sigma>-2. By [1 Corollary 3.12.3], it must be an odd cycle, contrary to a1>2a_1>2. Hence Γ\Gamma contains an induced quadrangle. Now Claim 1 and Lemma 2.3 give τ≤θ1≤b1−1\tau\le\theta_1\le b_1-1. Since b1=(τ+1)(σ−1)b_1=(\tau+1)(\sigma-1), we have σ≥2\sigma\ge2.

Claim 3. For any two vertices p,q∈V(Γ)p,q\in V(\Gamma) with d(p,q)=2d(p,q)=2,

δpq≥2c2σ−σ.(7)\delta_{pq}\ge\frac{2c_2}{\sigma}-\sigma. \tag*{(7)}

The average δ‾\overline{\delta} of δpq\delta_{pq} over all unordered pairs of vertices of Γ\Gamma at distance 2 equals the average of μΔ\mu_{\Delta} over all local graphs of Γ\Gamma.

Proof of Claim 3. By Claim 2, we have τ≤θ1≤b1−1\tau\le\theta_1\le b_1-1. Write u1=u1(θ1)u_1=u_1(\theta_1) and u2=u2(θ1)u_2=u_2(\theta_1). Equation (2) gives

u2=(θ1−τ)(θ1+σ)kb1≥0,u1−u2=(k−θ1)(θ1+1)kb1>0,(8)u_2=\frac{(\theta_1-\tau)(\theta_1+\sigma)}{kb_1}\ge0,\qquad u_1-u_2=\frac{(k-\theta_1)(\theta_1+1)}{kb_1}>0, \tag*{(8)}
η:=1−u2u1−u2=1+b1θ1+1≤1+b1τ+1=σ,2≤η≤σ.\eta:= \frac{1-u_2}{u_1-u_2}=1+\frac{b_1}{\theta_1+1}\le1+\frac{b_1}{\tau+1}=\sigma,\qquad2\le\eta\le\sigma.

Consider a normalized representation z↦z^z\mapsto\hat{z} associated to θ1\theta_1. Fix p,q∈V(Γ)p,q\in V(\Gamma) with d(p,q)=2d(p,q)=2. Let M=MpqM=M_{pq} and

Z=∑z∈V(M)z^.Z=\sum_{z\in V(M)}\hat{z}.

Since vertices of MM are pairwise at distance one or two in Γ\Gamma,

∥Z∥2=c2(1−u2)+c2δpq(u1−u2)+c22u2,\lVert Z\rVert^2=c_2(1-u_2)+c_2\delta_{pq}(u_1-u_2)+c_2^2u_2,
⟨Z,p^+q^⟩=2c2u1,∥p^+q^∥2=2(1+u2).\langle Z,\hat{p}+\hat{q}\rangle=2c_2u_1,\qquad\lVert\hat{p}+\hat{q}\rVert^2=2(1+u_2).

Applying Cauchy–Schwarz to ZZ and p^+q^\hat{p}+\hat{q} gives

(2c2u1)2≤2(1+u2)(c2(1−u2)+c2δpq(u1−u2)+c22u2).(2c_2u_1)^2\le2(1+u_2)\left(c_2(1-u_2)+c_2\delta_{pq}(u_1-u_2)+c_2^2u_2\right).

Since 1+u2>01+u_2>0 and u1−u2>0u_1-u_2>0, this is equivalent to

δpq≥c2(2u12/(1+u2)−u2)−(1−u2)u1−u2=c2−η−c2u1(η−2)1+u2.\delta_{pq}\ge\frac{c_2(2u_1^2/(1+u_2)-u_2)-(1-u_2)}{u_1-u_2}=c_2-\eta-\frac{c_2u_1(\eta-2)}{1+u_2}.

Moreover, using (3),

0≤u1(η−2)=σ−2σ−(θ1−τ)(θ1+2−σ)k(θ1+1)≤σ−2σ,0\le u_1(\eta-2)=\frac{\sigma-2}{\sigma}-\frac{(\theta_1-\tau)(\theta_1+2-\sigma)}{k(\theta_1+1)}\le\frac{\sigma-2}{\sigma},

since θ1≥τ\theta_1\ge\tau and θ1+2−σ≥a1+2>0\theta_1+2-\sigma\ge a_1+2>0. As u2≥0u_2\ge0 and η≤σ\eta\le\sigma, it follows that

δpq≥c2−σ−c2(σ−2)σ=2c2σ−σ.\delta_{pq}\ge c_2-\sigma-\frac{c_2(\sigma-2)}{\sigma}=\frac{2c_2}{\sigma}-\sigma.

Let S2S_2 be the set of unordered distance-two pairs of V(Γ)V(\Gamma). We count the number of induced diamonds (see Figure 2) in Γ\Gamma. Then

∑{p,q}∈S2(12c2δpq)=12∑x∈V(Γ)(12kb1⋅μΔx),\sum_{\{p,q\}\in S_2}\left(\frac{1}{2}c_2\delta_{pq}\right)=\frac{1}{2}\sum_{x\in V(\Gamma)}\left(\frac{1}{2}kb_1\cdot\mu_{\Delta_x}\right),

where the μ\mu-graph MpqM_{pq} has 12c2δpq\frac{1}{2}c_2\delta_{pq} edges, and the local graph Δx\Delta_x of Γ\Gamma at vertex xx has 12kb1\frac{1}{2}kb_1 unordered pairs of nonadjacent vertices. Thus we have

1∣S2∣∑{p,q}∈S2δpq=1v∑x∈V(Γ)μΔx,\frac{1}{|S_2|}\sum_{\{p,q\}\in S_2}\delta_{pq}=\frac{1}{v}\sum_{x\in V(\Gamma)}\mu_{\Delta_x},

where

∣S2∣=12vk2=vkb12c2.|S_2|=\frac{1}{2}vk_2=\frac{vkb_1}{2c_2}.

Claim 4. a1=0a_1=0.

Proof of Claim 4. Let δ‾\overline{\delta} be the average of δpq\delta_{pq} over all unordered pairs of the vertices of Γ\Gamma at distance 2. Then by Claim 1 and Claim 3, we have

2c2σ−σ≤δ‾≤min⁡{a1σ+1,a1(a1−1)b1}.(9)\frac{2c_2}{\sigma}-\sigma\le\overline{\delta}\le\min\left\{\frac{a_1}{\sigma+1},\frac{a_1(a_1-1)}{b_1}\right\}. \tag*{(9)}

Figure 2. Induced diamond

Since b1≤2c2b_1 \le2c_2 and σ≥2\sigma\ge2 (Claim 2), using (3), we have

2c2σ−σ≥b1σ−σ=a1−a1+1σ≥a1−12,b1≥a1+3.\frac{2c_2}{\sigma}-\sigma\ge\frac{b_1}{\sigma}-\sigma=a_1-\frac{a_1+1}{\sigma}\ge\frac{a_1-1}{2},\qquad b_1\ge a_1+3.

By (9), we have

a1−12≤δˉ≤min⁡{a13,a1(a1−1)a1+3}.(10)\frac{a_1-1}{2}\le\bar{\delta}\le\min\left\{\frac{a_1}{3},\frac{a_1(a_1-1)}{a_1+3}\right\}. \tag*{(10)}

Assume a1≥2a_1\ge2. The lower bound and first upper bound in (10) imply a1≤3a_1\le3. Then the lower bound and second upper bound in (10) give a1≥3a_1\ge3, hence a1=3a_1=3. By (10), we have δˉ=1\bar{\delta}=1. Then δˉ≤a1/(σ+1)\bar{\delta}\le a_1/(\sigma+1) implies σ=2\sigma=2. Hence b1=6b_1=6 by (3). By (9), δˉ≥c2−2\bar{\delta}\ge c_2-2, so c2≤3c_2\le3. Since b1≤2c2b_1\le2c_2, we have c2=3c_2=3.

Choose p,q∈V(Γ)p,q\in V(\Gamma) with d(p,q)=2d(p,q)=2. Note that the μ\mu-graph MpqM_{pq} has 3 vertices. Then (7) implies δpq≥1\delta_{pq}\ge1. It follows that MpqM_{pq} has at least two edges and δpq≥4/3\delta_{pq}\ge4/3, contradicting δˉ=1\bar{\delta}=1. Hence a1≤1a_1\le1.

Assume a1=1a_1=1. Then every local graph is 1-regular and every independent set in a local graph has at most k/2k/2 vertices. Note that Γ\Gamma contains no induced diamond and each μ\mu-graph contains no edges. Choose x,y,z∈V(Γ)x,y,z\in V(\Gamma) with d(x,z)=4d(x,z)=4 and d(x,y)=d(y,z)=2d(x,y)=d(y,z)=2. Then vertices in MxyM_{xy} and MyzM_{yz} form an independent set of Δy\Delta_y with 2c22c_2 vertices. Hence 2c2≤k/22c_2\le k/2. As a1=1a_1=1 and b1≤2c2b_1\le2c_2, we have k=b1+2≤2c2+2k=b_1+2\le2c_2+2. Then c2≤1c_2\le1, a contradiction. Hence a1=0a_1=0.

By Claim 4, a1=0a_1=0 and b1=k−1b_1=k-1. Assume Γ\Gamma is nonbipartite. Then Lemma 2.4 implies c2≤k/3c_2\le k/3. As b1≤2c2b_1\le2c_2, we have k−1=b1≤2c2≤2k/3k-1=b_1\le2c_2\le2k/3. Thus k≤3k\le3 and c2≤1c_2\le1, contrary to c2≥2c_2\ge2.

Proofs of Theorems 1.2 and 1.3

Lemma 4.1. Let Γ\Gamma be a 2-walk-regular graph with valency k≥3k\ge3, diameter D≥4D\ge4, and k2≤2kk_2\le2k. If c2=1c_2=1, then

(k,a1)=(3,0)or(4,1).(k,a_1)=(3,0)\quad\text{or}\quad(4,1).

In particular, if k≥5k\ge5, then c2≥2c_2\ge2.

Proof. Note that 1≤b1≤2c2=21\le b_1\le2c_2=2. As c2=1c_2=1, Γ\Gamma contains no induced diamond and every local graph is a disjoint union of cliques of size a1+1a_1+1. Since a1+1=k−b1a_1+1=k-b_1, we have k−b1∣kk-b_1\mid k, that is k−b1∣b1k-b_1\mid b_1. It follows that b1=2b_1=2, and k=3k=3 or 4.

Lemma 4.2. Let HH be a cubic 3-walk-regular graph with diameter DH≥3D_H\ge3 and girth at least six. Then DH≥4D_H\ge4 if and only if DL(H)≥4D_{L(H)}\ge4.

Proof. Assume DH≥4D_H\ge4 and consider a path x0x1x2x3x4x_0x_1x_2x_3x_4 with dH(x0,x4)=4d_H(x_0,x_4)=4. Since HH is 3-walk-regular, we have b3≠0b_3\ne0. Take a neighbor zz of x4x_4 with dH(x1,z)=4d_H(x_1,z)=4. Then dL(H)(x0x1,x4z)=4d_{L(H)}(x_0x_1,x_4z)=4. It follows that DL(H)≥4D_{L(H)}\ge4. If DH=3D_H=3, then HH is distance-regular, which is the Heawood graph (see [1 Theorem 7.5.1]). Since HH is bipartite with diameter three, any two edges have endpoints in the same bipartition class at distance at most two. Hence DL(H)≤3D_{L(H)} \le3.

Lemma 4.3. (i) For a 2-walk-regular graph Γ\Gamma with valency k=4k=4, diameter D≥4D \ge4 and (a1,c2)=(1,1)(a_1,c_2)=(1,1), there exists a unique cubic 3-walk-regular graph HH with diameter DH≥4D_H \ge4 and girth gH≥6g_H \ge6, such that Γ=L(H)\Gamma=L(H).

(ii) Conversely, for a cubic 3-walk-regular graph HH with diameter DH≥4D_H \ge4 and girth gH≥6g_H \ge6, the line graph L(H)L(H) is 2-walk-regular with valency 4, diameter DL(H)≥4D_{L(H)} \ge4 and (a1,c2)=(1,1)(a_1,c_2)=(1,1).

Proof. (i) Note that the local graph of Γ\Gamma consists of two disjoint edges. Let V(H)V(H) be the set of triangles of Γ\Gamma, and two vertices of HH are adjacent if the triangles share a common vertex. Then HH is cubic. Let NN be the triangle-vertex incidence matrix of Γ\Gamma, which is also the vertex-edge incidence matrix of HH. Then AΓ=NTN−2IA_{\Gamma}=N^{T}N-2I implies Γ=L(H)\Gamma=L(H).

A triangle in HH would give an extra triangle in Γ\Gamma, and an induced quadrangle in HH would give an induced quadrangle in Γ\Gamma. Hence gH≥5g_H \ge5. Since Γ=L(H)\Gamma=L(H) and DH+1≥DL(H)≥4D_H+1 \ge D_{L(H)} \ge4, we have DH≥3D_H \ge3.

Choose a path x0x1x2x3x_0x_1x_2x_3 in HH with dH(x0,x3)=3d_H(x_0,x_3)=3. Let x2x4x_2x_4 and x3x5x_3x_5 be extra edges. Note that dΓ(x0x1,x2x3)=2d_{\Gamma}(x_0x_1,x_2x_3)=2 and dΓ(x0x1,x2x4)=2d_{\Gamma}(x_0x_1,x_2x_4)=2. If dΓ(x0x1,x3x5)=2d_{\Gamma}(x_0x_1,x_3x_5)=2, then x1∼x5x_1\sim x_5, contradicting gH≥5g_H \ge5. Hence a2=1a_2=1 in Γ\Gamma. If HH contains an induced pentagon w0w1w2w3w4w0w_0w_1w_2w_3w_4w_0, then dΓ(w0w1,w2w3)=2d_{\Gamma}(w_0w_1,w_2w_3)=2 and w3w4,w2w6∈Γ2(w0w1)w_3w_4,w_2w_6 \in\Gamma_2(w_0w_1), where w2w6w_2w_6 is an extra edge, contrary to a2=1a_2=1. This shows gH≥6g_H \ge6.

Consider the vertex-edge incidence matrix of HH. Let

P=NNT=AH+3I,Q=NTN=AΓ+2I.P=NN^{T}=A_H+3I,\qquad Q=N^{T}N=A_{\Gamma}+2I.

For every ℓ≥1\ell\ge1, we have

Pℓ=NQℓ−1NT,Qℓ+1=NTPℓN.P^{\ell}=NQ^{\ell-1}N^{T},\qquad Q^{\ell+1}=N^{T}P^{\ell}N.

By the first identity, the diagonal of PℓP^{\ell} is a constant β0\beta_0, as the three edges incident with a vertex of HH form a triangle in Γ\Gamma. Let the entries of Qℓ+1Q^{\ell+1} at distance i≤2i \le2 in Γ\Gamma be γi\gamma_i. Then we successively determine entries βi\beta_i of PℓP^{\ell} at distance i=1,2,3i=1,2,3 in HH through

2β0+2β1=γ0,β0+2β1+β2=γ1,β1+2β2+β3=γ2.2\beta_0+2\beta_1=\gamma_0,\qquad\beta_0+2\beta_1+\beta_2=\gamma_1,\qquad\beta_1+2\beta_2+\beta_3=\gamma_2.

Since powers of AH=P−3IA_H=P-3I are linear combinations of powers of PP, the graph HH is 3-walk-regular. And Lemma 4.2 implies DH≥4D_H \ge4.

Assume Γ=L(H)\Gamma=L(H) with HH cubic and girth gH≥6g_H \ge6. Then each vertex of HH is incident with three edges. Hence each vertex of HH corresponds to a triangle in Γ\Gamma. As HH is triangle-free, every triangle of Γ\Gamma arises in this way. And two vertices of HH are adjacent if the triangles in Γ\Gamma share a common vertex. This shows the uniqueness of HH.

(ii) Conversely, Lemma 2.6 implies that L(H)L(H) is 2-walk-regular, and Lemma 4.2 implies DL(H)≥4D_{L(H)} \ge4. Since gH≥6g_H \ge6, the local graph of L(H)L(H) consists of two disjoint edges and a1=1a_1=1. Then L(H)L(H) contains no induced quadrangles and c2=1c_2=1.

Proof of Theorem 1.2. Assume c2≥2c_2 \ge2. Note that b1≤2c2b_1 \le2c_2. Then Γ\Gamma is bipartite by Theorem 1.1. We have b1=k−1b_1=k-1 and b2=k−c2b_2=k-c_2. Since b1≤2c2b_1 \le2c_2 and c2≤b2c_2 \le b_2 (Lemma 2.1), we have

(k−1)/2≤c2≤k/2.(k-1)/2 \le c_2 \le k/2.

If kk is even, then c2=k/2c_2 = k/2 and k≥4k \ge4. Then Γ\Gamma is a Hadamard graph by [1 Theorem 1.9.3], giving (i).

If kk is odd, then c2=(k−1)/2c_2 = (k - 1)/2 and k≥5k \ge5. Hence c2>k/3c_2 > k/3. Lemma 2.4 shows that Γ\Gamma is the 5-cube, giving (ii), or the incidence graph of a GDDDP(2,m;k;0,c2)(2,m;k;0,c_2). In the latter case, the vertices at distance two from a point are precisely the 2(m−1)2(m-1) points outside its group. Hence 2(m−1)=k2=kb1c2=2k2(m-1) = k_2 = \frac{kb_1}{c_2} = 2k, that is m=k+1m = k + 1. Lemma 2.5 shows that D=4D = 4, giving (iii).

If c2=1c_2 = 1, Lemma 4.1 gives (k,a1)=(3,0)(k,a_1) = (3,0) or (4,1)(4,1). In the cubic case, a1=0a_1 = 0 and c2=1c_2 = 1 show that the girth is at least five, giving (iv). In the quartic case, Lemma 4.3 gives (v).

Conversely, the 5-cube and Hadamard graphs are distance-regular, hence 2-walk-regular, with k2=2kk_2 = 2k and k2=2k−2k_2 = 2k - 2, respectively. The graphs in (iii) are 2-walk-regular with k2=2kk_2 = 2k by Lemma 2.5. For the graphs in (iv), Lemma 2.6 gives 2-walk-regularity. The girth condition implies (a1,c2)=(0,1)(a_1,c_2) = (0,1), so k2=6=2kk_2 = 6 = 2k. For the graphs in (v), Lemma 4.3 gives 2-walk-regularity and (k,a1,c2)=(4,1,1)(k,a_1,c_2) = (4,1,1), so k2=8=2kk_2 = 8 = 2k.

Proof of Theorem 1.3. Apply Theorem 1.2 to distance-regular graphs with k2≤2kk_2 \le2k. The only possible cases are (i), (ii), (iv) and (v). The result follows from the classifications of distance-regular graphs of valency 3 or 4 (see [1 Theorem 7.5.1] and [2 Theorem 1.1]).

Proof of Theorem 1.4

Lemma 5.1. Let Γ\Gamma be a 2-walk-regular graph with valency k≥3k \ge3, diameter D≥4D \ge4, and v≤4k+4v \le4k+4 vertices. Then k2≤2kk_2 \le2k.

Proof. Choose two vertices x,yx,y with d(x,y)=4d(x,y) = 4. Note that {x},Γ(x),Γ2(x),Γ(y),{y}\{x\},\Gamma(x),\Gamma_2(x),\Gamma(y),\{y\} are pairwise disjoint. Hence we have

2+2k+k2≤v≤4k+4,(11)2 + 2k + k_2 \le v \le4k + 4, \tag*{(11)}

that is k2≤2k+2k_2 \le2k + 2. Suppose k2>2kk_2 > 2k. Then 2c2+1≤b1≤k−12c_2 + 1 \le b_1 \le k - 1, and

k2=kb1c2≥2k+kc2>2k+2,k_2 = \frac{kb_1}{c_2} \ge2k + \frac{k}{c_2} > 2k + 2,

a contradiction.

Lemma 5.2. Let Γ\Gamma be a 2-walk-regular graph with valency k≥3k \ge3, diameter D≥4D \ge4, and v≤4k+4v \le4k+4 vertices. If c2=1c_2 = 1, then k=3k = 3 and Γ\Gamma is the incidence graph of a GDDDP(2,4;3;0,1)(2,4;3;0,1).

Proof. Lemma 5.1 gives k2≤2kk_2 \le2k. Then we only need to consider (iv) and (v) of Theorem 1.2.

In (v) of Theorem 1.2, k=4k = 4 and Γ=L(H)\Gamma= L(H), where HH is a cubic 3-walk-regular graph with diameter at least four and girth at least six. We have ∣H2(x)∣=6|H_2(x)| = 6, and ∣V(H)∣≥14|V(H)| \ge14 by (10). Then

v=∣E(H)∣=32∣V(H)∣≥21>4k+4.v = |E(H)| = \frac{3}{2}|V(H)| \ge21 > 4k + 4.

In (iv) of Theorem 1.2, we have k=3k = 3 and girth at least five. Then a1=0a_1 = 0, c2=1c_2 = 1 and k2=6k_2 = 6. Note that kv=2∣E(Γ)∣kv = 2|E(\Gamma)|, that is 2∣v2 \mid v. Equation (10) implies v∈{14,16}v \in\{14,16\}. Lemma 2.1 gives b2≥c2=1b_2 \ge c_2 = 1, so a2=2−b2∈{0,1}a_2 = 2 - b_2 \in\{0,1\}.

Suppose a2=1a_2 = 1. For every vertex xx, each edge in Γ2(x)\Gamma_2(x) determines a unique pentagon through xx. Thus each vertex lies in ka2/2=3a2ka_2/2 = 3a_2 pentagons and the total number of pentagons is 3va25\frac{3va_2}{5}, that is 5∣v5 \mid v, which contradicts v∈{14,16}v \in\{14,16\}.

It follows that a2=0a_2 = 0 and b2=2b_2 = 2. Take two vertices x,yx,y of Γ\Gamma with d(x,y)=4d(x,y) = 4. Note that there are at most kb1=6kb_1 = 6 edges between Γ(y)\Gamma(y) and Γ2(x)\Gamma_2(x), and k2b2=12k_2b_2 = 12 edges between Γ2(x)\Gamma_2(x) and Γ3(x)\Gamma_3(x). It follows that ∣Γ3(x)∖Γ(y)∣≥12−63=2|\Gamma_3(x) \setminus\Gamma(y)| \ge\frac{12-6}{3} = 2 and v≥1+k+k2+(k+2)+1=16v \ge1 + k + k_2 + (k+2) + 1 = 16. Then we have v=16v = 16, Γ(y)⊆Γ3(x)\Gamma(y) \subseteq\Gamma_3(x) and ∣Γ3(x)∖Γ(y)∣=2|\Gamma_3(x) \setminus\Gamma(y)| = 2. Note that there are six edges between Γ2(x)\Gamma_2(x) and each of Γ(y)\Gamma(y) and Γ3(x)∖Γ(y)\Gamma_3(x) \setminus\Gamma(y). We have c3(x,w)=2c_3(x,w)=2 for w∈Γ(y)w \in\Gamma(y), and c3(x,z)=3c_3(x,z)=3 for z∈Γ3(x)∖Γ(y)z \in\Gamma_3(x) \setminus\Gamma(y). Since c2=1c_2=1, each vertex in Γ2(x)\Gamma_2(x) has exactly one neighbor in each of Γ(y)\Gamma(y) and Γ3(x)∖Γ(y)\Gamma_3(x) \setminus\Gamma(y). Then the partition Π(x)={{x},Γ(x),Γ2(x),Γ(y),Γ3(x)∖Γ(y),{y}}\Pi(x)=\{\{x\},\Gamma(x),\Gamma_2(x),\Gamma(y),\Gamma_3(x) \setminus\Gamma(y),\{y\}\} has the distribution diagram as in Figure 3. Since Γ\Gamma is bipartite with v=16v=16 and k2=6k_2=6, every vertex has a unique vertex at distance four. Hence Γ\Gamma is the incidence graph of GDDDP(2,4;3;0,1)(2,4;3;0,1).

Figure 3. Distribution diagram of the incidence graph of GDDDP(2, 4; 3; 0, 1)

Proof of Theorem 1.4. By Lemma 5.1, v≤4k+4v \le4k+4 implies k2≤2kk_2 \le2k. If c2=1c_2=1, then Lemma 5.2 applies. For c2≥2c_2 \ge2, the results follow from Theorem 1.2.

Funding This work was supported by the National Natural Science Foundation of China (No. 12371338) and the Key Project in Natural Science Research of Anhui Provincial Department of Education (No. 2023AH050268).

Data Availability No data was used for the research described in the article.

Declarations

Conflict of interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

References

  1. [1]A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
  2. [2]A. E. Brouwer and J. H. Koolen, The distance-regular graphs of valency four, J. Algebraic Combin. 10 (1999), 5–24.DOI
  3. [3]M. Cámara, E. R. van Dam, J. H. Koolen and J. Park, Geometric aspects of 2-walk-regular graphs, Linear Algebra Appl. 439 (2013), 2692–2710.DOI
  4. [4]M. Conder and R. Nedela, Symmetric cubic graphs of small girth, J. Combin. Theory Ser. B 97 (2007), 757–768.DOI
  5. [5]C. Dalfó, E. R. van Dam, M. A. Fiol, E. Garriga and B. L. Gorissen, On almost distance-regular graphs, J. Combin. Theory Ser. A 118 (2011), 1094–1113.
  6. [6]C. Dalfó, M. A. Fiol and E. Garriga, On k-walk-regular graphs, Electron. J. Combin. 16 (2009), #R47.DOI
  7. [7]E. R. van Dam, J. H. Koolen and H. Tanaka, Distance-regular graphs, Electron. J. Combin. (2016), #DS22.DOI
  8. [8]W. Jin, J. H. Koolen and C. Lv, Amply regular graphs with μ close to half the valency and group divisible designs, arXiv:2605.25754, 2026.arxiv.org/abs/2605.25754
  9. [9]J. H. Koolen and J. Park, Shilla distance-regular graphs, European J. Combin. 31 (2010), 2064–2073.arxiv.org/abs/0902.3860
  10. [10]J. H. Koolen and J. Park, Distance-regular graphs with a₁ or c₂ at least half the valency, J. Combin. Theory Ser. A 119 (2012), 546–555.DOI
  11. [11]Z. Qiao, S. F. Du and J. H. Koolen, 2-Walk-regular digraphs from group divisible designs, Electron. J. Combin. 23 (2016), #P2.51.DOI
  12. [12]Z. Qiao, J. H. Koolen and J. Park, 2-Walk-regular graphs with a small number of vertices compared to the valency, Linear Algebra Appl. 510 (2016), 10–24.DOI
  13. [13]Z. Qiao, J. Park and J. H. Koolen, On 2-walk-regular graphs with a large intersection number c₂, European J. Combin. 80 (2019), 224–235.DOI

Paper details

vlnc:W_s7ypzmab
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents