Distance-Regular Graphs with ci = bd−i and Antipodal Double Covers

Distance-Regular Graphs with ^c

= b

and Antipodal Double Covers

MAKOTO ARAYA [email protected]

Department of Computer Science, Shizuoka University, Hamamatsu Shizuoka, 432–8011 Japan

AKIRA HIRAKI [email protected]

Division of Mathematical Sciences, Osaka Kyoiku University, Kashiwara Osaka 582–8582, Japan

Received March 24, 1995; Revised May 1, 1997

Abstract. LetΓbe a distance-regular graph of diameterdand valencyk >2. Suppose there exists an integers withd≤2ssuch thatci=bd−ifor all1≤i≤s. ThenΓis an antipodal double cover.

Keywords: distance-regular graph, antipodal double cover, box, brox.

1. Introduction

Throughout this paper, we assumeΓis a connected finite undirected graph without loops or multiple edges. We identifyΓwith the set of vertices. For verticesuandxinΓ, let∂(u, x) denote the distance betweenuandxinΓ, i.e., the length of a shortest path connectingu andx. Letd=d(Γ)denote the diameter ofΓ, i.e., the maximal distance between any two vertices inΓ. Let

Γ_i(u) ={y∈Γ|∂(u, y) =i}. For verticesuandxinΓat distancei, let

Ci(u, x) = Γi−1(u)∩Γ1(x), Ai(u, x) = Γi(u)∩Γ1(x) and Bi(u, x) = Γi+1(u)∩Γ1(x).

A graphΓis called a distance-regular graph if for any two verticesuandxinΓat distance i, the numbers

ci=|Ci(u, x)|, ai=|Ai(u, x)| and bi=|Bi(u, x)|

depend only on the distance∂(u, x) =irather than on individual vertices. When this is the case we call numbersc_i,a_iandb_ithe intersection numbers ofΓ, in particulark=b₀ is called valency ofΓ.

Lethbe an integer with 1 ≤ h ≤ d, v andxvertices in Γ at distanceh. Take any u∈C_h(x, v). The following are well known basic properties which we use implicitly in this paper.

(1) Γ1(x) =Ch(v, x)∪Ah(v, x)∪Bh(v, x), (2) Bh−1(u, x)⊇Bh(v, x),

(3) C_h−1(u, x)⊆C_h(v, x),

(4) C_h(α, γ)⊆B_d−h(β, γ)for anyγ∈Γ_h(α)∩Γ_d−h(β)with∂(α, β) =d, (5) The numbersk_i:=|Γ_i(x)|depend only oni,

(6) The numbersp_i,j^h :=|Γ_i(v)∩Γ_j(x)|depend only oni, jandh=∂(v, x).

In particular, we have

(1⁰) k=ci+ai+bi for i= 0, . . . , d, (2⁰) k=b₀> b₁≥ · · · ≥b_d−1≥1, (3⁰) 1 =c₁≤c₂≤ · · · ≤c_d≤k, (4⁰) c_h≤b_d−h for 1≤h≤d.

The reader is referred to [3] or [4] for the general theory of distance-regular graphs.

A distance-regular graphΓof diameterdis called an antipodal double cover (of its folded graph), if and only ifc_i=b_d−i, fori= 1, . . . , d.

For more details on antipodal graphs see [5], and§4.2 of [4].

The main result of this paper is the following:

Theorem 1 LetΓbe a distance-regular graph of diameterdand valencyk >2. Suppose there exists an integerswithd≤2ssuch thatci =bd−ifor all1≤i≤s. ThenΓis an antipodal double cover.

In [1], we have already obtained the special case of the main theorem of this paper, i.e., a distance-regular graph ofb_t= 1,d≥2tand valencyk >2is an antipodal double cover, which is one of important facts to prove our theorem.

In general, it is well known that p_d,dⁱ_−i = b_i · · · b_d−1

cd−i · · · c1

= b_i

cd−i ·p_d,dⁱ⁺¹_−i−1 ≥ p_d,dⁱ⁺¹_−i−1 and thus

kd = p_d,d⁰ ≥ p_d,d¹₋₁ ≥ · · · ≥ p_d,0^d = 1.

Hence we obtain the following corollary immediately from our theorem.

Corollary 1 If there exists an integertwith2t ≤ dsuch thatp_d,d^t_−t = 1,thenΓis an antipodal double cover.

By the definition,Γis an antipodal double cover if and only ifp_d,dⁱ_−i= 1for all0≤i≤d.

We use the following terminology in this paper.

Definition Letu, v, xandybe vertices inΓ.

(1) We write the “ triangle inequalities on (u, v, x, y)” for the triangle inequalities of (u, v, y)and of(u, x, y).

(2) The quadruple(u, v, x, y)is called an(h, j)-box if

∂(u, v) = 1, ∂(u, x) =h−1, ∂(x, y) =j,

∂(v, x) =h, ∂(v, y) =h−j, ∂(u, y) =h−j+ 1.

(3) The quadruple(u, v, x, y)is called aj-brox if

∂(u, v) = 2, ∂(u, x) =d−1, ∂(x, y) =j,

∂(v, x) =d, ∂(v, y) =d−j, ∂(u, y) =d−j+ 2.

A(d,1)-box is called a box that was a key to prove the theorem in [1]. Notice that there are many boxes in an antipodal distance-regular graphΓof diameterd≥3; namely, givenu, y with∂(u, y) =d, there is a one to one correspondence betweenv∈Γ₁(u)andx∈Γ₁(y) such that(u, v, x, y)is a box. Moreover, ifΓhas a box, then alsoΓhas a(d, j)-box, i.e., for y⁰ ∈Γd−j(v)∩Γj−1(y)the quadruple(u, v, x, y⁰)is a(d, j)-box. Whence an antipodal distance-regular graph has a(d, j)-box for anyj.

On the other hand, a distance-regular graph which is an antipodal double cover never contains aj-brox(u, v, x, y)by observing the(u, v, x).

HHHHHH

HHHHHH

HHHHHH

HHHHHH

a box: a(d, j)-box:

•

•

•

•

y v

x

u ^d−1

d−1 d

d 1

1

•

•

•

•

y v

x

u ^d−1

d−j d−j+ 1

d j

1

HHHH

HHHH

HHHH

HHHH

HHHH

HHHH

an(h, j)-box: aj-brox:

•

•

•

•

y v

x

u ^h−1

h−j h−j+ 1

h j

1

•

•

•

•

y v

x

u ^d−1

d−j d−j+ 2

d j

2

When we characterize graphs, it is important to consider their substructures. One of the characterization of antipodal distance-regular graphs is that they have a box. These configurations are useful tools when we investigate if a graph is antipodal or not as we see

§2, [1] or [2]. Readers who are familiar with distance distribution diagrams may read some of proofs easily, however, we can do without diagrams.

2. Proof of the Theorem

Throughout this section, we assumeΓis not an antipodal double cover to derive a con- tradiction. ThenΓcannot have any boxes, and must have some broxes in Lemma3and Lemma5.The existence and nonexistence of these configurations lead to the inequality in Lemma6that causes a contradiction.

For the cases= 1,the theorem is trivial and well-known. We may assumes≥2.

SupposeΓis not an antipodal double cover. Then we have

cj =bd−j for all 1≤j≤s, cs+16=b_d−(s+1) for someswith^d₂ ≤s < dand lett:=d−s.

Ifb_t= 1,thenΓis an antipodal double cover from [1]. So we may assumeb_t≥2.

Lemma 1 (1)p^d_{d, j}^−j = 1 for all 0≤j ≤s and p_d,s+1^t−1 ≥ 2, (2)a_t−1< a_t.

Proof: Using the well known formula ofp^l_i,j p^d_d,j^−j = bd−j· · ·bd−1

cj · · · c1

=

½= 1 if 0≤j ≤s

≥2 if j=s+ 1

from our assumption. This implies b_t−1=c_s+1p^t_d,s⁻¹₋₁≥2c_s+1.Thus we obtain a_t−1 ≤ k−b_t−1 ≤ k−2c_s+1

≤ k−ct−cs = at+bt−cs = at.

If the equality holds, thent= 1andb_t=c_s=c_s+1=c_t= 1.This contradictsb_t≥2.

Lemma 2 Letu, v, αandβbe vertices inΓwith∂(u, v) = 1and∂(α, β) =d.

(1) Ifcj =cj+1,then we have

Aj(v, x) ⊆ Aj+1(u, x) for any x ∈ Γj+1(u)∩Γj(v).

(2) For all integerjwith1≤j≤s.We have

C_j(α, x) = B_d−j(β, x) for any x ∈ Γ_j(α)∩Γ_d−j(β).

In particular, ift≤j≤s,thenAj(α, x) =Ad−j(β, x).

(3) We haveΓs+1(β)∩Γt(α)6=φand

Cs+1(β, y) = Bt(α, y) for any y ∈ Γs+1(β)∩Γt(α).

In particular,c_s+1=b_t=c_s.

Proof: (1)(2) The assertions follow from basic properties and our assumptions.

(3) Take anyx∈Γs+1(β)∩Γt−1(α).Sincecs+1< bt−1,we have y ∈ B_t−1(α, x)−C_s+1(β, x).

Sincey6∈C_s+1(β, x)andy6∈C_t−1(α, x) =B_s+1(β, x),we obtainy∈A_s+1(β, x).This meansy∈Γ_s+1(β)∩Γ_t(α),i.e.,Γ_s+1(β)∩Γ_t(α)6=φ.

Next we show thatC_s+1(β, y) =B_t(α, y).Take anyz∈C_s+1(β, y).From the triangle inequalities on(α, β, y, z),we have

t = d−s = ∂(β, α)−∂(β, z) ≤ ∂(α, z) ≤ ∂(α, y) +∂(y, z) = t+ 1.

PPPPPPPPP

PPPP α

β

y

z t

d 1

s

•

•

•

•

This implies∂(α, z)∈ {t, t+ 1}.Suppose∂(α, z) =t.Then we have y ∈ A_t(α, z) = A_s(β, z)

from (2). This contradictsy∈Γs+1(β).Hence we obtain∂(α, z) =t+ 1and Cs+1(β, y) ⊆ Bt(α, y).

The assertion follows from

c_s ≤ c_s+1 = |C_s+1(β, y)| ≤ |B_t(α, y)| = b_t = c_s.

Lemma 3 (1) There exists no(d, j)-box for any1≤j≤s.

(2) There exists no(d−i+ 1,2)-box for any1≤i≤s−1.

Proof: (1) We prove by induction onj.

SupposeΓhas a box (u, v, x, y).Take anyp ∈ Γ_s(v)∩Γ_t−1(y).Then we havep ∈ Γ_s+1(u)∩Γ_t(x)by the triangle inequalities on(u, v, y, p)and on(x, v, y, p).

HHHH

HHHH HHHH

•

•

•

• •

u

v

x

y p

1 s+ 1 t 1

s t−1

From Lemma 1 (2), there existsq∈At(x, p)−At−1(y, p).Then by Lemma 2 q ∈ A_t(x, p) = A_s(v, p) ⊆ A_s+1(u, p).

Let{y^∗} = Γd(u)∩Γt−1(q)as p_d,t^s+1₋₁ = 1.Then we obtain ∂(v, y^∗) = d−1 by the triangle inequalities on(v, q, u, y^∗).And let {x^∗} = Bd−1(v, y^∗).Also we obtain

∂(q, x^∗) =tby the triangle inequalities on(q, v, y^∗, x^∗).

HHHH

HHHH HHHH

•

•

•

• •

u

v

x^∗

y^∗ q

1 s+ 1 t 1

s t−1

This impliesx=x^∗as{x, x^∗} ⊆ Γd(v)∩Γt(q)andp_d,t^s = 1.

Then{y, y^∗} ⊆ Bd−1(u, x)andy6=y^∗as∂(y^∗, q) =t−16=∂(y, q).This contradicts b_d−1= 1.HenceΓdoes not have a box.

Now we assume 2 ≤ j ≤ s and there exists a (d, j)-box (u⁰, v⁰, x⁰, y⁰) in Γ. Take z∈B_d−j+1(u⁰, y⁰)as2≤j.Then we have

z ∈ Bd−j+1(u⁰, y⁰) ⊆ Bd−j(v⁰, y⁰) = Cj(x⁰, y⁰) by Lemma 2 (2).

u⁰•

v⁰•

x⁰

•

•z PPPPPPPPPPPPPPPPPP

d−j+ 1 d−1

d d−j+ 2

1 j−1

This implies(u⁰, v⁰, x⁰, z)is a(d, j−1)-box, contradicting our inductive assumption.

(2) Suppose that there exists a(d−i+ 1,2)-box(u, v, x, y)for some1≤i≤s−1.

u•

v•

•x

•y PPPPPPPPPPPPPPPPPP

d−i−1 d−i

d−i+ 1 d−i

1 2

Let{v^∗} = Γd(v)∩Γi−1(x)as p^d_{d, i}⁻ⁱ⁺¹₋₁ = 1. Then we have∂(u, v^∗) = d−1and

∂(y, v^∗) = i+ 1from the triangle inequalities on(u, v, x, v^∗)and on(y, v, x, v^∗).This implies(u, v, v^∗, y)is a(d, i+ 1)-box, contradicting (1).

Lemma 4 Letαandβbe vertices inΓwith∂(α, β) =dandx∈Γt(α)∩Γs(β).

(1)

Ad(α, β) = Bs(x, β) and Ad(β, α) = Bt(x, α).

In particular, we havebs=ad=bt≥2.

(2)a1= 0, (3)bs+1=bs=ct.

Proof: (1) Suppose there existsz ∈ Ad(α, β)−Bs(x, β).Then we have∂(x, z) = s, by the triangle inequalities on(x, α, β, z)andz 6∈ B_s(x, β).This means that{β, z} ∈ Γ_d(α)∩Γ_s(x).However, this contradictsp_d,s^t = 1.Thus we obtainA_d(α, β) ⊆ B_s(x, β).

On the other hand, if there existsy∈B_s(x, β)−A_d(α, β),then(y, β, α, x)is a(d, t)-box, contradicting Lemma 3 (1). Hence we haveA_d(α, β) = B_s(x, β).

In the same way, we obtainA_d(β, α) =B_t(x, α).

(2) Supposea₁>0.Take anyγ∈A_d(α, β)andδ∈A₁(β, γ).Then we haveδ∈A_d(α, β) asb_d−1= 1.This meansB_s(x, β)contains an edge{γ, δ}from (1). Let

m= max{j =∂(u, v)|Bj(u, v)contains an edge}. By our observation,

s ≤ m < d−1.

Letuandvbe vertices inΓwith∂(u, v) =mandBm(u, v)contains an edge{w, z}. We can take

u⁰ ∈ Bm+1(w, u) ⊆ Bm(v, u).

From the triangle inequalities on(u⁰, v, w, z)and the maximality ofm, we have∂(u⁰, z) = m+ 1.Since

1 = | {v} | ≤ |C_m+1(u, z)−C_m+1(u⁰, z)| = |C_m+1(u⁰, z)−C_m+1(u, z)|, there existsy∈C_m+1(u⁰, z)−C_m+1(u, z).Then we have∂(y, u) =m+1and∂(w, y) = 2 by the triangle inequalities on(y, u⁰, z, u)and observing(u⁰, y, w).Thus(u, u⁰, w, y)is an (m+ 2,2)-box.

u•

u⁰•

•w

•y PPPPPPPPPPPPPPPPPP

m m+ 1

m+ 2 m+ 1

1 2

Since t ≤ s ≤ m,this contradicts Lemma 3 (2). Thereforea₁must be zero.

(3) Fixγ∈Cd(β, α)andδ∈Bd−1(γ, β).Then∂(α, δ) =das otherwise(α, γ, δ, β)is a box.

α•

γ•

•δ

•β PPPPPPPPPPPPPPPPPP

d−1 d

d

1 1

Sincea_d >1 =b_d−1,we havey∈A_d(α, β)−B_d−1(γ, β).By the triangle inequality of(γ, α, y),we obtainy∈A_d−1(γ, β)asy6∈B_d−1(γ, β).Sincea₁= 0and considering (γ, δ, y),we have∂(δ, y) = 2.

Letξ∈Γt(γ)∩Γs−1(y).We claim that∂(α, ξ) =t+ 1and∂(δ, ξ) =s+ 1.

HHHH

HHHH HHHH

•

•

•

• •

α

γ

δ

y ξ

1 2

t s−1

We have∂(α, ξ) =t+ 1by the triangle inequalities on(α, γ, y, ξ).

From the triangle inequalities on(δ, γ, y, ξ),we have∂(δ, ξ)∈ {s, s+ 1}.Let{γ^∗}= Bd−1(γ, y).Then∂(ξ, γ^∗) =sandδ6=γ^∗by the triangle inequalities on(γ^∗, γ, y, ξ)and considering(y, δ, γ^∗).

HHHH

HHHH

HHHH HHHH

HHHH

HHHH•

•

•

•

ξ γ

y

δ 2

t

s−1 d

•

•

•

•

ξ γ

y

γ^∗ 1

t

t−1 d

If∂(δ, ξ) =s,then{δ, γ^∗} ⊆Γ_d(γ)∩Γ_s(ξ)with∂(γ, ξ) =t.This contradictsp_d,s^t = 1.

Hence we obtain∂(δ, ξ) =s+ 1as claimed.

Next we show thatCt(γ, ξ) = Bs+1(δ, ξ). Take any w ∈ Ct(γ, ξ).Then we obtain

∂(α, w) =tand∂(δ, w)∈ {s+ 1, s+ 2}from the triangle inequalities on(α, γ, ξ, w) and on(δ, γ, ξ, w).

HHHH

HHHHHHHH HHHH

HHHHHHHH•

•

•

•

w γ

ξ

α t+ 1

t−1

1 1

•

•

•

•

w γ

ξ

δ s+ 1

t−1

1 d

If∂(δ, w) =s+ 1,thenw∈Γ_t(α)∩Γ_s+1(δ)with∂(α, δ) =d.Hence we have ξ ∈ Bt(α, w) = Cs+1(δ, w)

from Lemma 2 (3). This contradicts∂(δ, ξ) =s+ 1.Thus we have∂(δ, w) =s+ 2,i.e., C_t(γ, ξ)⊆B_s+1(δ, ξ).The assertion follows from

c_t = |C_t(γ, ξ)| ≤ |B_s+1(δ, ξ)| = b_s+1 ≤ b_s = c_t.

Lemma 5 There exists ani-brox for all2≤i≤s.

Proof: We prove by induction ons−i.

Suppose there exists nos-brox inΓ. Letxandvbe vertices inΓwith∂(x, v) =d.Take y∈Γs(x)∩Γt(v)andw∈Ad(x, v).Then from Lemma 4 (1), we have∂(y, w) =t+ 1.

Take anyu∈B_t+1(y, w).

HHHH

HHHH

HHHH

HHHHHH

•

•

•

•

• u

w

v

x

y 1

1

t+ 2 d

d

t

s

Then∂(x, u) =das otherwise(u, v, x, y)is ans-brox. Thus we obtain Bt+1(y, w) ⊆ Ad(x, w)− {v}, i.e., bt+1 ≤ ad−1.

On the other hand, we have

bt+1 ≥ bs+1 = bs = ad

from Lemma 4 (1)(3). This is a contradiction. Hence there exists-broxes.

For the case s = 2,the lemma is already proved. We may assume s ≥ 3.Suppose 2 ≤i ≤ s−1and there exists noi-brox to derive a contradiction. From the inductive assumption, we have an(i+ 1)-brox(u⁰, v⁰, x⁰, y⁰).Fix anyw⁰ ∈C2(u⁰, v⁰).

HHHH

HHHHHH

HHHH HHHH

•

•

•

•

• u⁰

w⁰

v⁰

x⁰

y⁰ d−1

d−i+ 1

d

d−i−1

i+ 1

It is clear that∂(w⁰, y⁰) =d−iby the triangle inequalities on(w⁰, u⁰, v⁰, y⁰)and that

∂(x⁰, w⁰) =das otherwise(w⁰, v⁰, x⁰, y⁰)is a(d, i+ 1)-box.

Claim: Ci+1(x⁰, y⁰) ⊆ Bd−i(w⁰, y⁰)−Bd−i+1(u⁰, y⁰).

Take anyz⁰∈C_i+1(x⁰, y⁰).From Lemma 2 (2), we obtain

z⁰ ∈ Ci+1(x⁰, y⁰) = B_d−(i+1)(v⁰, y⁰), i.e., ∂(v⁰, z⁰) = d−i.

It is clear that ∂(u⁰, z⁰) ∈ {d−i, d−i+ 1, d−i+ 2} by the triangle inequality of (u⁰, y⁰, z⁰).If∂(u⁰, z⁰) =d−i,then(z⁰, y⁰, u⁰, v⁰)is a(d−i+ 1,2)-box. This contradicts Lemma 3 (2). If∂(u⁰, z⁰) =d+ 2−i,then(u⁰, v⁰, x⁰, z⁰)is ani-brox. This contradicts our assumption. Thus∂(u⁰, z⁰) =d−i+ 1, i.e.,z⁰6∈Bd−i+1(u⁰, y⁰).

u⁰•

w⁰•

x⁰

•

z⁰ • PPPPPPPPPPPPPPPPPP

d−1

d d−i+ 1

1 i

We have∂(w⁰, z⁰)∈ {d−i, d−i+ 1}by the triangle inequalities on(w⁰, u⁰, v⁰, z⁰).If

∂(w⁰, z⁰) =d−i,then(u⁰, w⁰, x⁰, z⁰)is a(d, i)-box, contradicting Lemma 3 (1). Hence we obtain∂(w⁰, z⁰) =d−i+ 1,i.e.,z⁰ ∈Bd−i(w⁰, y⁰).Whence the claim is proved.

This implies

ci+1 ≤ bd−i−bd−i+1. However we have

c_i+1 ≥ c_i = b_d−i. This is a contradiction asi≥2.

Lemma 6 We have

bj−cd−j+1 ≤ bj+1−cd−j for all 1 ≤ j ≤ s−1.

Proof: There exists a 2-brox (u, v, x, y) from Lemma 5. Fix any w ∈ C2(u, v)and z∈C2(x, y).Then we have∂(w, y) =d−1from the triangle inequalities on(w, u, v, y), and∂(x, w) =das otherwise(w, v, x, y)is a(d,2)-box. Similarly,∂(z, v) =d−1and

∂(u, z) =d.We obtain∂(w, z) =das otherwise(u, w, x, z)is a box.

HHHH

HHHH

HHHH XXXXX XXXXXXX

XXXXX

XXXXXXX

•

•

•

•

v u

y x

d d

d−1

d−2

•

•

•

•

•

• v

u w

y x d z

d

d−1 d−1

d

Fix anyp∈Γj−1(y)∩Γd−j−1(v)for1≤j≤s−1.Then from the triangle inequalities on (p, y, v, u), (p, y, v, w), (p, y, v, z) and (p, v, y, x), we obtain that p ∈ Γd−j+1(u) ∩ Γd−j(w) ∩ Γj(z) ∩ Γj+1(x).

HHHH

HHHH

HHHH XXXXX

XXXXXXX

•

•

• u w v

d−j+ 1 d−j d−j−1

•

•

• x z y j+ 1 j j−1

•p

In order to prove the statement, we will show that

B_j(z, p)−B_j+1(x, p) ⊆ C_d−j+1(u, p)−C_d−j(w, p).

Take anyq∈Bj(z, p)−Bj+1(x, p).It is clear that∂(y, q) =jby the triangle inequalities on(y, z, p, q).

First, we will proveq6∈Cd−j(w, p)and∂(w, q) =d−j.

Suppose q ∈ Cd−j(w, p). We have ∂(x, q) = j + 1 by the triangle inequalities on (x, w, p, q)andq 6∈ Bj+1(x, p).SinceCd−j(w, p) ⊆ Cd−j+1(u, p),we obtain(u, w, x, q) is a(d, j+ 1)-box. This contradicts Lemma 3 (1). Henceq 6∈ Cd−j(w, p).Sinceq 6∈

Cj(z, p) =Bd−j(w, p),we obtain∂(w, q) =d−j.

Then we obtain ∂(v, q) = d−j −1 by the triangle inequalities on(v, w, p, q)and q 6∈ C_j(z, p) ⊆ C_j+1(x, p) = B_d−j−1(v, p). Also we have∂(x, q) = j + 1from the triangle inequalities on(x, v, p, q)andq6∈B_j+1(x, p).

HHHH

HHHH

HHHH XXXXX

XXXXXXX

•

•

• u w v

d−j d−j−1

•

•

• x z y j+ 1 j+ 1

• j d−1

q Next we will proveq∈C_d−j+1(u, p).

From the triangle inequalities on(u, w, y, q),we have∂(u, q) ∈ {d−j, d−j+ 1}. Supposeq 6∈ C_d−j+1(u, p)to derive a contradiction. Then∂(u, q) = d−j + 1. Let {y^∗} = Γ_d(u)∩Γ_j−1(q)as p^d_{d, j}^−j+1₋₁ = 1.By the triangle inequalities on(w, u, q, y^∗), we get∂(w, y^∗) =d−1and thus let{z^∗}=B_d−1(w, y^∗).We obtain∂(q, z^∗) =jand

∂(v, z^∗) = d−1by the triangle inequalities on(q, w, y^∗, z^∗)and on(v, w, q, z^∗).Then

∂(u, z^∗) =das otherwise(u, w, z^∗, y^∗)is a box.

Let{x^∗}=Bd−1(v, z^∗).Also we get∂(q, x^∗) =j+ 1,by the triangle inequalities on (q, v, z^∗, x^∗).Since{x, x^∗} ⊆Γd(v)∩Γj+1(q)andp^d_{d, j+1}^−j−1= 1,we havex= x^∗. As

∂(q, z) =j+ 16=j =∂(q, z^∗),we havez6=z^∗.However{z, z^∗} ⊆Bd−1(u, x).This contradictsbd−1= 1.Hence we obtainq ∈ Cd−j+1(u, p).Therefore the lemma is proved.

Proof of Theorem 1. From Lemma 6 and Lemma 4 (3), we have b₁−c_d ≤ b₂−c_d−1 ≤ · · · ≤ b_s−c_t+1 ≤ 0.

On the other hand, from Lemma 4 (1)(2)

b₁−c_d = (k−1)−(k−a_d) = −1 +a_d ≥ 1.

We have a contradiction. This completes the proof of Theorem 1.

Acknowledgments

The authors would like to thank S. Iwamoto, T. Koishi, H. Nakano and S. Sugitani for their valuable comments.

References

1. M. Araya, A. Hiraki and A. Juriˇsi´c, “Distance-regular graphs withbt= 1and antipodal double-covers,” J.

Combin. Th. (B) 67 (1996), 278–283.

2. M. Araya, A. Hiraki and A. Juriˇsi´c, “Distance-regular graphs withb2= 1and antipodal covers,” Europ. J.

Combinatorics 18 (1997), 243–248.

3. E. Bannai and T. Ito, Algebraic Combinatorics I, Benjamin-Cummings, California, 1984.

4. A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, Heidel- berg, 1989.

5. A. Gardiner, “Antipodal covering graphs,” J. Combin. Th. (B) 16 (1974), 255–273.