Parallelogram-free distance-regular graphs having completely regular strongly regular subgraphs

DOI 10.1007/s10801-009-0167-2

Parallelogram-free distance-regular graphs having completely regular strongly regular subgraphs

Hiroshi Suzuki

Received: 29 December 2007 / Accepted: 19 January 2009 / Published online: 4 February 2009

© Springer Science+Business Media, LLC 2009

Abstract Let=(X, R)be a distance-regular graph of diameterd. A parallelogram of lengthiis a 4-tuplexyzwconsisting of vertices ofsuch that∂(x, y)=∂(z, w)= 1,∂(x, z)=i, and∂(x, w)=∂(y, w)=∂(y, z)=i−1. A subsetY ofXis said to be a completely regular code if the numbers

πi,j = |j(x)∩Y| (i, j∈ {0,1, . . . , d})

depend only oni=∂(x, Y )andj. A subsetY ofXis said to be strongly closed if {x|∂(u, x)≤∂(u, v), ∂(v, x)=1} ⊂Y,wheneveru, v∈Y.

Hamming graphs and dual polar graphs have strongly closed completely regular codes. In this paper, we study parallelogram-free distance-regular graphs having strongly closed completely regular codes. Let be a parallelogram-free distance- regular graph of diameterd≥4 such that every strongly closed subgraph of diameter two is completely regular. We show thathas a strongly closed subgraph of diameter d−1 isomorphic to a Hamming graph or a dual polar graph. Moreover if the covering radius of the strongly closed subgraph of diameter two isd−2,itself is isomorphic to a Hamming graph or a dual polar graph. We also give an algebraic characterization of the case when the covering radius isd−2.

Keywords Distance-regular graph·Association scheme·Homogeneity· Completely regular code

H. Suzuki (

Department of Mathematics and Computer Science, International Christian University, Mitaka, Tokyo 181-8585, Japan

e-mail:[email protected]

1 Introduction

The study of completely regular codes in a distance-regular graph has a long history [3,5]. Most of the completely regular codes studied are those with large minimum distance because of the requirements to apply the theory to error-correcting codes.

Recently Brouwer et al. [2] studied a special class of completely regular codes in a Q-polynomial distance-regular graph satisfying extremal conditions from a different point of view. Let us call these codes extremal. These extremal codes afford induced structure of aQ-polynomial distance-regular graph and hence they are necessarily connected as a graph or minimum distance one. Independently, we studied the Ter- williger algebra with respect to a subset in [9]. The thin condition of the principal module of this Terwilliger algebra is equivalent to the complete regularity of the base subset. We also gave a sufficient condition, called tight, that the module generated by an end-point-zero vector is thin. In the case of the principal module, if the subset is extremal, then it is tight.

In a recent paper [10], H. Tanaka classified all extremal completely regular codes in certain classical association schemes. For example if the underlying graph is a dual polar graph, then extremal codes are strongly closed. In the literature, one also finds weak-geodesically closed used in place of strongly closed.

In this paper, we study a converse, i.e., we classify parallelogram-free distance- regular graphs having strongly closed completely regular codes. To state our re- sults, we make a few definitions. For notation, terminology and the general theory of distance-regular graphs, we refer the reader to [1].

Let=(X, R)be a connected graph of diameterdwith vertex setXand edge set R. For verticesxandy,∂(x, y)denotes the distance betweenxandy, i.e., the length of a shortest path connectingx andy. More generally, for eachx∈Xand a subset S⊂Xwe write∂(x, S)=min{∂(x, s)|s∈S}.

For a vertexu∈Xandj∈ {0,1, . . . , d}, let

_j(u)= {x∈X|∂(u, x)=j}and(u)=1(u).

A subsetY ofXis said to be completely regular, or a completely regular code, if the following numbers

π_i,j = |_j(x)∩Y| (i, j∈ {0,1, . . . , d})

depend only oni=∂(x, Y )andj. We writeγ_i=π_i,i. ForY ⊂X, the numbert (Y )= max{∂(x, Y )|x∈X}is called the covering radius ofY, andw(Y )=max{∂(x, y)| x, y∈Y}is called the width ofY.

For two verticesuandv∈Xwith∂(u, v)=j, let C(u, v)=C_j(u, v) = _j−1(u)∩(v), A(u, v)=A_j(u, v) = _j(u)∩(v), and B(u, v)=B_j(u, v) = _j+1(u)∩(v).

A connected graph is said to be distance-regular or a distance-regular graph if the cardinalitiesc_j = |C(u, v)|,a_j = |A(u, v)|andb_j= |B(u, v)| depend only on j=∂(u, v)for allj∈ {0,1, . . . , d}. These numberscj’s,aj’s andbj’s are called the intersection numbers of.

A subsetY of the vertex setXis often called a code, but in this paper, it is also regarded as the induced subgraph on Y. A nonempty subset Y of X is said to be strongly closed if

C(u, v)∪A(u, v)⊂Y for allu, v∈Y.

In this caseY is also called a strongly closed subgraph. For two verticesx andy, x, y denotes the smallest strongly closed subgraph containingx andy. Note that since the intersection of two strongly closed subgraphs is strongly closed and itself is a strongly closed subgraph containingxandy,x, y always exists.

A parallelogram of lengthiis a 4-tuplexyzwconsisting of vertices ofsuch that

∂(x, y)=∂(z, w)=1,∂(x, z)=i, and∂(x, w)=∂(y, w)=∂(y, z)=i−1.

A parallelogram of length 2 is isomorphic toK_2,1,1. If a distance-regular graph does not have a parallelogram of length 2, then it is said to have order(s, t )for some positive integerss andt, as every edge is contained in a maximal clique of constant sizes+1, and every vertex is contained in exactlyt+1 maximal cliques.

In particular, the valencyk=s(t+1)and the neighborhood(x)of each vertexxis isomorphic to a disjoint union oft+1 cliques of sizes. Ifc₂=1, thenis of order (s, t )for some positive integerssandt. Ifa₁=0 thenis of order(1, k−1).

A distance-regular graph=(X, R)of diameterd is said to be a regular near polygon if it is of order(s, t )for some integerssandt, and for every maximal clique Land a vertexx∈Xwith∂(x, L)=i < d,|_i(x)∩L| =1. A regular near polygon having the property that no maximal clique is contained in_d(x)for anyx∈X is called a regular near 2d-gon. A regular near 4-gon is called a generalized quadran- gle. A regular near polygon is often defined as an incidence structure, and in that case our regular near polygon is called the collinearity graph of a regular near polygon, or the point graph of it. See [1, Section 6.4].

If a graph does not contain parallelograms of any length, it is called parallelogram free. A regular near polygon is parallelogram free, and the parallelogram-free condi- tion is closely related to the existence of strongly closed subgraphs. See Theorem2.2.

Throughout this paper by strongly regular graphs we mean distance-regular graphs of diameter two, hence connected.

Now we state our main results.

Theorem 1.1 Let=(X, R)be a parallelogram-free distance-regular graph of di- ameterd≥4 such thatb₁> b₂anda₂=0. Suppose every strongly closed subgraph Cof diameter 2 is completely regular. Then the following hold.

(i) is a regular near polygon withc2>1, and for every pair of verticesx, y at distanced−1,has a strongly closed subgraphY of diameterd−1 containing x andy.

(ii) The covering radiust (C)of each strongly closed subgraphCof diameter 2 is at leastd−2, and

(a) Ift (C)=d−2, thenis isomorphic to a Hamming graph or a dual polar graph.

(b) Ift (C)≥d−1, then every strongly closed subgraphY of diameterd−1 is isomorphic to a Hamming graph or a dual polar graph.

Whenq=1 andd≥4, we can prove thatitself is isomorphic to a Hamming graph without assuming that the covering radius is d −2 by [6, 11]. See the last section.

We have the following characterization of the case that a strongly regular subgraph is completely regular with covering radiusd−2.

Theorem 1.2 Let=(X, R)be a parallelogram-free distance-regular graph of or- der(s, t )and diameterd≥4. Supposeb1> b2anda2=0. Letq=c2−1. Then the following are equivalent.

(i) There is a completely regular codeC of covering radius d−2 such that the induced subgraph onC is strongly regular.

(ii) There is a strongly closed completely regular codeC of width 2 and covering radiusd−2.

(iii) Every strongly closed subgraph of diameter 2 is completely regular with cover- ing radiusd−2.

(iv) Every strongly closed subgraph of diameter 2 is completely regular with cover- ing radiusd−2 and that it is a generalized quadrangle.

(v) q=0 andhas eigenvalues−t−1 ands−t /q.

(vi) is isomorphic to a Hamming graph or a dual polar graph.

2 Preliminaries

Lemma 2.1 ([1, Remark on page 86], [8, Lemma 2.6]) Letbe a strongly regular graph witha₂=0, and letube a vertex of. Then the induced subgraphon₂(u) is connected of diameter at most three.

Theorem 2.2 ([12, Proposition 6.7], [8, Theorem 1.1]) Let = (X, R) be a distance-regular graph of diameterd, and letmbe a positive integer such that 2≤ m≤d. Assume thatcontains no parallelogram of lengthifor anyi=2, . . . , m+1 and thatb₁> b₂. In addition assume one of the following:

(i) m=2,c₂>1 anda₂=0, (ii) c₂>1 anda₁=0, (iii) m=2 andc2=1, (iv) c2=1 anda1=0, or

(v) cm+1=1.

Then for any verticesx, y∈Xwith∂(x, y)≤m, the diameter of the strongly closed subgraphx, y is∂(x, y). In particular, ifa₂=0, then for any verticesx, y∈X with∂(x, y)=2, there is a strongly closed subgraph of diameter 2 containingxand y.

Lemma 2.3 ([12, Lemma 6.9], [8, Lemma 4.1]) Let = (X, R) be a distance- regular graph with diameter d≥3. Suppose contains no parallelogram of any length. Letx be a vertex andY a strongly closed subgraph of diameter 2. Suppose u∈i(x)∩Y and i+2(x)∩Y = ∅with i+2≤d. Then for ally∈Y, we have

∂(x, y)=i+∂(u, y).

3 Terwilliger algebras and completely regular codes

Let=(X, R)be a connected graph of diameterd andCa subset ofXwith width w=w(C) and covering radius t =t (C). Let C_i = {x∈X|∂(x, C)=i}for i∈ {0,1, . . . , t}.

LetV =C^X=Span(xˆ|x∈X)be a vector space over the complex number field consisting of the set of column vectors with rows indexed by the elements ofX, and

ˆ

xdenotes the unit vector whosex-entry is 1 and 0 otherwise.

For eachi=0,1, . . . , d, letAi∈MatX(C)be thei-th adjacency matrix defined by

(A_i)_x,y=

1 ∂(x, y)=i, 0 otherwise.

We callA=A1the adjacency matrix of.

Fori∈ {0,1, . . . , t},E_i^∗=E_i^∗(C)∈MatX(C)are defined as follows.

(E_i^∗)_x,y=

1 ifx=yandx∈C_i, 0 otherwise.

The matrixE_i^∗induces the projection onto the subspaceE_i^∗V =Span(xˆ|x∈Ci).

Definition 3.1 The Terwilliger algebraT =T(C)of a connected graph=(X, R) associated with a subsetCofXis a matrix subalgebra overCof MatX(C)generated byAtogether withE^∗₀, E₁^∗, . . . , E^∗_t, wheret=t (C). AT-moduleWis aT-invariant linear subspace ofV. A nonzeroT-moduleWis said to be irreducible ifW does not contain proper nonzeroT-modules. An irreducibleT-moduleWis said to be thin if dimE_i^∗W≤1 for everyi=0,1, . . . , t.

Definition 3.2 Let=(X, R)be a connected graph, andC a nonempty subset of X. Let 1C=

x∈Cxˆ∈V =C^X. ThenC is said to be a completely regular code if T(C)1Cis a thin irreducibleT(C)-module.

Note that ifis a distance-regular graph, the definition of complete regularity in the introduction coincides with the one given above. The proof is straightforward.

See [9, Proposition 7.2] and [5].

Let=(X, R)be a connected graph. Then it is immediate that is distance- regular if and only if it is regular and every singleton{x}withx∈X is completely regular. It is not difficult to show that if is distance-regular of diameterd, then every edge{x, y}withx, y∈Xis completely regular if and only ifa₁=a₂= · · · = a_d−1=0, i.e.,is almost bipartite or bipartite.

Thin Irreducible Modules. Let=(X, R)be a distance-regular graph of valency kand diameterd. LetA_i be thei-th adjacency matrix andA=A₁. Then there is a polynomialv_i(λ)∈C[λ]of degree exactlyisuch thatv_i(A)=A_i. Letk_i =v_i(k).

Thenk_i= |_i(x)| for everyx ∈X. Letθ0> θ1>· · ·> θ_d be distinct eigenvalues ofAand letE0, E1, . . . , E_dbe the primitive idempotents ofC[A]corresponding to each of the distinct eigenvalues. Then each column of E_i is an eigenvector of the same eigenvalueθ_i of A, andAE_i =θ_iE_i. Let m(θ_i)=tr(Ei). Thenm(θ_i)is the multiplicity ofθi as an eigenvalue ofA. Set = {θ0, θ1, . . . , θd}.

LetC be a nonempty subset of X andT =T(C). We consider an irreducible T-moduleW such thatE₀^∗W=0, which is called a module of endpoint 0.

We review some facts proved in [9].

Letv=E₀^∗vbe a nonzero vector. Set

ρv(λ)= 1

|X| d

i=0 tvAiv

v² vi(λ)

k_i ∈R[λ]. The following is called the inner distribution of the vectorv.

a(v)=

tvA₀v v² , . . . ,

tvA_iv v² , . . . ,

tvA_dv v²

.

By definition, ifw=w(C)is the width ofC, then the degree ofρv(λ)is at most w. On the other hand by direct computation we have

E_iv²

v² =ρv(θi)m(θi).

SinceC[A]v=Span(E0v, E₁v, . . . , E_dv), we have

dimC[A]v≥d+1−(# of roots ofρv(λ)in )≥d+1−w(C).

Setr=r(v)=dimC[A]v−1. The numberr(v)is called the dual degree ofv. If 1C

is the characteristic vector ofC, we writer(C)forr(1C)and call the dual degree of C. Now we have the following.

Theorem 3.1 ([9, Theorem 1.1]) Let = (X, R) be a distance-regular graph of diameterd, andCa nonempty subset ofX. LetE₀^∗=E₀^∗(C)andv=E₀^∗va nonzero vector. Then the following hold.

(i) dimC[A]v+w(C)≥d+1.

(ii) If dimC[A]v+w(C)=d+1, thenT(C)vis a thin irreducibleT(C)-module.

A nonzero vectorv∈E₀^∗V satisfying the condition in Theorem3.1(ii) is called a tight vector. WhenE₀^∗V is spanned by tight vectors, we callCa tight code.

The case thatvis the characteristic vector 1CofCis also studied in [2]. See also [4].

Corollary 3.2 ([2, Theorem 1]) Let=(X, R)be a distance-regular graph of di- ameterd, andCa nonempty subset ofXwith dual degreer=r(C). Ifr+w(C)=d, thenCis a completely regular code. Moreover, we havet=rin this case.

Note that the condition in the corollary can be checked if we havea(1C)together with the set of eigenvalues ofA. In the literature, the inner distributiona(1C)is also called the inner distribution of the codeCand denoteda(C).

4 Completely regular subgraphs

Proposition 4.1 Let=(X, R)be a distance-regular graph of valencykand diam- eterd. LetCbe a subset ofXcontained in a proper strongly closed subgraphY of . In addition assume that|_i(z)∩C|depends only oniwhenever∂(z, C)=1. Then Cis strongly closed.

Proof First note that the maximal valency ofY is notk. Suppose not, and letmbe the diameter ofY. Thenc_m+a_m=kandb_m=0. This impliesm=d andY is not regular. This contradicts Theorem 1.1 in [7].

Letx, y∈Csuch that∂(x, y)=. Since the maximal valency ofY is less thank, there is a vertexu∈X\Y adjacent tox. Letv∈C. SinceC⊂Y andY is strongly closed∂(u, v)=∂(x, v)+1. Letz∈(x)such that∂(z, y)≤. We claim thatz∈C.

Suppose not. Then∂(z, C)=1 and the following hold.

v∈C

∂(x, v)+ |C| =

v∈C

∂(u, v)=

v∈C

∂(z, v).

Since∂(z, v)≤∂(x, v)+1. The above holds only if∂(z, v)=∂(x, v)+1 holds for allv∈C. Sincey∈Cand∂(z, y)≤=∂(x, y), this is absurd. Thus we proved the

claim. HenceC is strongly closed.

An induced subgraph onY of a graph=(X, R)is called weakly closed if the distance in the subgraph is equal to the distance in.

Corollary 4.2 Let=(X, R) be a distance-regular graph of diameter d. Let C be a weakly closed distance-regular subgraph in of diameter , and u, v∈C with∂(u, v)=. In addition assume that |_i(z)∩C|depends only oni whenever

∂(z, C)=1. If bothuandvare contained in a proper strongly closed subgraphY of , thenC⊂Y andCis strongly closed.

Proof By Proposition4.1, it suffices to show thatC⊂Y. SinceC is connected for eachw∈C, there is a pathu=u₀∼u₁∼ · · · ∼u_m=winC. Since the diameter of Cis,Cis weakly closed andY is strongly closed,C∩(u)⊂YandC∩(v)⊂Y. SinceCis distance-regular and weakly closed, there is a vertexv1∈((v)∪ {v})∩C such that∂(u1, v1)=. Sincev1∈Y, we can proceed by induction to showw∈Y.

Lemma 4.3 Let=(X, R)be a distance-regular graph of diameterd. Let 1≤m≤ d−1 be an integer. Suppose foru, v∈Xwith∂(u, v)=m, there is a strongly closed subgraphCof diametermcontaininguandvandCis completely regular. Then the parametersπ_i,j ofCare determined bymand the parameters of.

Proof Since C is strongly closed in , the parameters of C and hence the inner distribution ofC is determined by the parameters of andm. Now the assertion

follows from [9, Corollary 10.3].

5 Completely regular strongly regular subgraphs

In this section, we study parallelogram-free distance-regular graphs having com- pletely regular strongly regular subgraphs. The goal is to establish the following re- sult.

Theorem 5.1 Let=(X, R)be a parallelogram-free distance-regular graph of di- ameterd≥4 such thatb1> b2anda2=0. Suppose every strongly closed subgraph Cof diameter 2 is completely regular. Letc2=q+1. Thenis a regular near poly- gon,q≥1 andc_i=_i

1

qfori∈ {1,2, . . . , d−1}. Moreover if the covering radius of Cisd−2, thenc_d=_d

1

qandis a regular near 2d-gon.

We first remark that under the hypothesis of Theorem5.1, for two verticesx, y with∂(x, y)=2, there is a strongly closed subgraphx, y of diameter 2 con- tainingxandyby Theorem2.2.

Hypothesis 5.1 Let=(X, R)be a parallelogram-free distance-regular graph of diameterd ≥4 such thatb1> b2anda2=0. Every strongly closed subgraphC of diameter 2 is completely regular.

Lets=a₁+1 andt=b₁/s. Thenin Hypothesis5.1is of order(s, t ).

Lemma 5.2 Under Hypothesis5.1, for everyi≤d−2 andu∈Xwith∂(u, C)=i, γ_i=γ_i(u)= |C∩_i(u)| =1,α_i=α_i(u)= |C∩_i+1(u)| =κ=a₂+c₂. In partic- ular, the covering radius ofCis at leastd−2 and the parametersγi andαi ofC as a completely regular code do not depend on the choice of strongly closed subgraphs of diameter 2 up toi≤d−2.

Proof Letx, y∈C with∂(x, y)=2. Sincei≤d−2, there is a vertexu∈_i(x)∩ i+2(y). Then by Lemma2.3, we have the desired conclusion. SinceCis completely regular, this is the case for allu∈Xwith∂(u, C)=i.

Lemma 5.3 Under Hypothesis5.1, C is a generalized quadrangle. In particular c₂>1.

Proof Sinceis parallelogram free andCis strongly closed,Cis of order(s, τ )for some integerτ. Letu∈C. Suppose that there are adjacent verticesv, w∈2(u)∩C such thatA(v, w)⊂2(u). Letx∈B(u, w). SinceCis strongly closed,∂(v, x)=2.

LetC=v, x . Sinceγ₂=1 and v, w∈C∩₂(u), ∂(u, C)=1. Let {y} = (u)∩C. Thenv, wand all vertices inC∩2(u)are in(y), which is absurd as {v, w} ∪A(v, w)is a maximal clique. HenceCis a generalized quadrangle.

Lemma 5.4 Under Hypothesis5.1, is a regular near polygon. Moreover if the covering radius ofCisd−2, thenis a regular near 2d-gon.

Proof LetLbe a maximal clique and∂(u, L)=i≤d−1 for some vertexu. We will show that|_i(u)∩L| =1. We may assume thati≥2 asLis a maximal clique. By way of contradiction assume that two verticesvandware ini(u)∩L.

First assume that_i+1(u)∩L= ∅. Letx∈C(u, v). Then∂(x, w)=2. LetC= x, w . Then either∂(u, C)=i−1 or∂(u, C)=i−2. The first case does not occur as otherwise∂(x, w)=1 by Lemma5.2. Suppose∂(u, C)=i−2. By Lemma5.3, we have a contradiction as we assumed that_i+1(u)∩L= ∅. This part also proves that if the covering radius ofC is d−2, there is no maximal cliqueL such that

∂(u, L)=d.

Next assume that_i+1(u)∩L= ∅. Letx∈_i+1(u)∩L andy∈C(u, v). Then

∂(x, y)=2. LetC=x, y . Sincev, w∈C, this contradicts Lemma5.2.

Lemma 5.5 Letq=c₂−1. Under Hypothesis5.1the following hold.

c_i+1−1=(c₂−1)ci,andc_i+1=1+q+· · ·+qⁱ= i+1 1

q

for alli≤d−2. (1) Moreover, if every strongly closed subgraphC of diameter 2 is of covering radius d−2, then (1) holds fori=d−1 as well.

Proof Letu, v, w∈Xwith∂(u, v)=i+1≤d andw∈C(u, v). We count the num- ber of pairs in the following set.

N= {(x, y)|x∈C(u, w), y∈C(x, v)\ {w}}.

First there arec_i choices ofxand then for eachx∈C(u, w), there arec₂−1 choices ofy. Hence we have|N| =(c₂−1)ci.

Next lety ∈C(u, v)\ {w}. Since is a regular near polygon by Lemma5.4,

∂(y, w)=2. LetY be the strongly closed subgraph of diameter 2, containingyand w. Since{y, w} ⊂i(u)andv∈Y∩i+1(u),∂(u, Y )=i−1 ifi≤d−2 ori=d−1 and every strongly closed subgraphCof diameter 2 is of covering radiusd−2. By Lemma5.2, there exists a vertexxsuch that_i−1(u)∩Y= {x}and thaty, w∈(x).

Thereforexis the unique vertex inC(y, w)∩i−1(u). Hence(x, y)∈N and|N| = c_i+1−1.

Sinceq=c₂−1 andc_i+1=qc_i+1, we have the formula forc_i+1by induction.

Proof of Theorem 5.1 Since C is a generalized quadrangle with a₂ =0 by Lemma 5.3, c2≥2 and q ≥1. Now we have the assertions by Lemma 5.4 and Lemma5.5.

Proof of Theorem1.1 By Theorem5.1c₂>1 andis a regular near polygon. Since a2=0,a1=0. Hence for every pair of verticesx, yat distanced−1,has a strongly closed subgraphY of diameterd−1 containingx andyby Theorem2.2. LetY be a strongly closed subgraph of diameterd−1 in. ThenY is a regular near 2(d−1)- gon withc_i=_i

1

q. Hence it is with classical parameters(d−1, q,0, a1+1). NowY is isomorphic to a Hamming graph or a dual polar graph ifd≥4 by Theorem 9.4.4 in [1]. The covering radius ofCis at leastd−2 by Lemma5.2and the result for the case the covering radius isd−2 follows similarly using the characterization in [1,

Theorem 9.4.4].

6 Tight completely regular codes of small width

In this section, we consider the case that a subsetCof small widthw≤2 becomes a completely regular code with smallest covering radiusd −w or 1C is tight that satisfies the condition in Corollary3.2.

Lemma 6.1 LetCbe a subset of a distance-regular graph=(X, R)of diameter d≥2. Letvbe a non-zero vector such that supp(v)⊂C. Let

ρv(λ)= 1

|X| d

i=0

η_ivi(λ)

ki ∈R[λ], whereη_i=η_i(v)=^tvA_iv v² . Then the following hold.

(i) Ifw(C)=1, then

ρv(λ)= 1

|X|b₀(b0+η1λ).

(ii) Ifw(C)=2, then ρv(λ)= 1

|X|b0b1

(b₀(b₁−η₂)+(η₁b₁−η₂a₁)λ+η₂λ²).

Proof Since

v0(λ)=1, v1(λ)=λ, andc2·v2(λ)=λ²−a1λ−b0,

the formulas above follow by direct computation using the fact thatη₀=1 andη_i=0

for alli > w(C).

Corollary 6.2 LetC be a subset of a distance-regular graph=(X, R)of order (s, t )of diameterd≥2. Let 1Cbe the characteristic vector ofC. Then the following hold.

(i) SupposeCis a maximal clique of sizes+1. Then ρ1C(λ)= 1

|X|(t+1)(t+1+λ).

(ii) SupposeCis strongly regular and strongly closed. In addition assume thatc₂+ a₂=(q+1)swithq=c₂−1, i.e.,Cis a generalized quadrangle. Then

ρ1C(λ)= 1

|X|(t+1)t(qλ+t−qs)(λ+t+1).

Proof (i) is immediate. For (ii),η0=1, η1=(q+1)s and η2=qs². Hence the

formula is immediate.

Proposition 6.3 Let=(X, R)be a distance-regular graph of order(s, t )of diam- eterd ≥3. SupposeC is a strongly closed generalized quadrangle in . Then the following are equivalent.

(i) has eigenvalues−t−1 ands−t /q, whereq=c₂−1.

(ii) Cis completely regular with covering radiusd−2.

Moreover if (i), (ii) hold, then every maximal cliqueC₁ is completely regular with covering radiusd−1.

Proof This is a direct consequence of Theorem 3.1, Corollary 3.2 and Corol-

lary6.2.

Proof of Theorem1.2 (iv)⇒(iii)⇒(ii)⇒(i) is clear, and (vi)⇒(v) is well-known. See [1, p. 261, p. 276].

(i)⇒(ii): Since the diameter ofCis two, it is weakly closed. Hence by Corollary4.2, Cis strongly closed.

(ii)⇒(iii): Letρ(λ)=ρ1C(λ). Sinceρ(λ)is determined byκ1= |(x)∩C| =c2+a2

andκ2= |2(x)∩C| =(c2+a2)(c2−a2−s)/c2,ρdoes not depend on the choice of strongly closed subgraph. Moreover by (ii), two distinct eigenvalues ofare the roots ofρ. Therefore, every strongly closed subgraph of diameter 2 is completely regular with covering radiusd−2.

(iii)⇒(iv): We need to show that the induced subgraph onC is a generalized quad- rangle. This follows from Lemma5.3.

(v)⇒(iv): Sincehas an eigenvalue−t−1, every maximal clique of sizes+1 is a completely regular code with covering radiusd−1. LetC be a strongly closed subgraph of diameter 2. Then every maximal clique of sizes+1 contained inC is completely regular with covering radius 1. SinceC is of order(s, τ )with a suitable choice of an integerτ,Cis a generalized quadrangle. In particularq=0 asa₂=0.

Note that ifY is a maximal clique andx∈C\Y,|(x)∩Y| =1 asY is maximal.

Henceρ_Cis as in Corollary6.2andρ_C has two eigenvalues−t−1 ands−t /qas roots. Therefore,Cis completely regular with covering radiusd−2.

(iv)⇒(vi): This is a direct consequence of Proposition6.3and Theorem1.1.

7 Remarks

For the caseq=1, the following two propositions cover most of our results. We only sketch their proofs.

Theorem 7.1 Letbe a parallelogram-free distance-regular graph of order(s, t ) withc₂=2,a₂=2(s−1)and c₃=3 withs >1. If the diameterd≥3, thenis isomorphic to the Hamming graphH (d, s+1).

Proof We proceed by induction ond. Ifd=3, then by [6, Corollary],is isomorphic toH (3, s+1). Note that we do not need the assumptions=3 asis parallelogram free. Suppose the assertion holds ford−1. By Theorem2.2, there is a strongly closed subgraphof diameter d−1 in. By induction hypothesis, is isomorphic to H (d−1, s+1)withd≥4. Now by [6, Theorem 1], there is a(d−1)-error correcting completely regular code of covering radiusd in aH (n, s+1)withs+1≥3. These are uniformly packed codes classified by H. van Tilborg [11] and the only possibility

forisH (d, s+1).

Corollary 7.2 Letbe a parallelogram-free distance-regular graph of order(s, t ), diameterd≥4 withc₂=2. Supposecontains a strongly regular (vertex induced) subgraph with parameters(κ, λ, μ). Ifκ=μand π_i,j= |_j(x)∩C|depends only oni=∂(x, C)andj whenever(i, j )=(1,1), (1,2)or(2,2). Thenis isomorphic to the Hamming graphH (d, s+1).

Proof By our assumption, c₂>1 and a₂=0. By Theorem 2.2, for each pair of distance two there is a strongly closed subgraph of diameter two containing the pair. Hence by Corollary4.2,C is strongly closed. Now by Lemma2.3,π_1,1=1, π1,2=κ=c2+a2andπ2,2=1. Hence by the proof of Lemma5.3,Cis a generalized quadrangle anda2=2(s−1). By mimicking the proof of Lemma5.5,c3=3. We are now ready to apply Theorem7.1to conclude thatis isomorphic toH (d, s+1).

The consideration of the caseq=1 above suggests us to classify distance-regular graphs of order(s, t )of diameterd≥4 with the following parameters:

ci=1+q+ · · · +qⁱ⁻¹, ai=ci(s−1)for alli∈ {1,2, . . . , d−1} withq≥2 ands >1.

The results in this paper also suggest problems to characterize distance-regular graphs by a given completely regular subgraph. Since_d(x)is always completely regular, this problem is connected to the problem to characterize distance-regular

graphs by the structure of_d(x). We close this paper by giving a possible improve- ment of the result of this paper.

Replace the hypothesis ‘parallelogram-free’ in Theorem5.1and Corollary5.1 by the following:

is of order(s, t )and every maximal clique is completely regular.

References

1. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin (1989) 2. Brouwer, A.E., Godsil, C.D., Koolen, J.H., Martin, W.J.: Width and dual width of subsets in polyno-

mial association schemes. J. Comb. Theory A 102, 255–271 (2003)

3. Delsarte, P.: An algebraic approach to the association schemes of coding theory. Philips Research Reports Supplements 1973, No.10

4. Hosoya, R., Suzuki, H.: Tight distance-regular graphs with respect to subsets of width two. Eur. J.

Comb. 28, 61–74 (2007)

5. Neumaier, A.: Completely regular codes. Discrete Math. 106–107, 353–360 (1992)

6. Nomura, K.: Distance-regular graphs of Hamming type. J. Comb. Theory B 50, 160–167 (1990) 7. Suzuki, H.: On strongly closed subgraphs of highly regular graphs. Eur. J. Comb. 16, 197–220 (1995) 8. Suzuki, H.: Strongly closed subgraphs of a distance-regular graph with geometric girth five. Kyushu

J. Math. 50, 371–384 (1996)

9. Suzuki, H.: The Terwilliger algebra associated with a set of vertices in a distance-regular graph. J. Al- gebr. Comb. 22, 5–38 (2005)

10. Tanaka, H.: Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs. J. Comb. Theory A 113, 903–910 (2006)

11. van Tilborg, H.C.A.: Uniformly packed codes. Ph.D. thesis, Eindhoven (1976). http://

alexandria.tue.nl/extra1/PRF2B/7602641.pdf

12. Weng, C.: Weak-geodesically closed subgraphs in distance-regular graphs. Graphs Comb. 14, 275–

304 (1998)