Graphs and Combinatorics (1999) 15 : 417±428

Graphs and Combinatorics ( Springer-Verlag 1999

Distance-regular Graphs of the Height h Akira Hiraki* Division of Mathematical Sciences, Osaka Kyoiku University, Kashiwara, Osaka 582± 8582, Japan. e-mail: [email protected]

Abstract. The height of a distance-regular graph of the diameter d is de®ned by h ˆ d maxf j j pd; j 0 0g. We show that if G is a distance-regular graph of diameter d, height h > 1 d and every pd; h -graph is a clique, then h A fd ÿ 1; dg.

1. Introduction Distance-regular graphs have a lot of substructures with high regularity. Sometimes they have distance-regular subgraphs. For example, there exist a lot of Johnson subgraphs in a Johnson graph. We are very much interested in this fact and believe that studying the substructures of distance-regular graphs are important. The simplest distance-regular graph is a clique that is a graph any two of its vertices are adjacent. It is well known that a local graph G 1 …x† is a disjoint union of cliques of size a1 ‡ 1 for all vertices x in a distance-regular graph G without the induced subgraph K2; 1; 1 . The case does occur if c2 ˆ 1. On the other hand the following result is known. (See [2, Proposition 5.5.2].) Let G be a distance-regular graph of diameter d and i be an integer with 1 < i < d. If every ci‡1 -graph is a clique, then ci‡1 ˆ 1. This result might suggest that there is no distance-regular graphs where every pi;t j -graph is a clique of size at least 2 for given i; j; t. However, we have several interesting examples. For the Johnson graphs J…3d ÿ 1; d† and J…3d ‡ 1; d†, every pi;t j -graph is a clique of size d for …t; i; j† ˆ …d; d; d ÿ 1† and …t; i; j† ˆ …d; d; d†, respectively. It is known that the distance 2-graph of a generalized Odd graph, is also distance-regular and its every pi;t j -graph is a clique for …t; i; j† ˆ …0; d; d†; …d; d; 1†. Problem 1.1. Find a distance-regular graph such that every pi;t j -graph is a clique of size at least 2 for given i; j; t.

*

Supported in part by a grant of Japan Society for Promotion of Science

418

A. Hiraki

d Let h :ˆ maxf j j pd; j 0 0g which is called the height of a distance-regular graph. d In the above examples, every pd; h -graph is a clique. Conversely the author d knows no distance-regular graph such that every pd; h -graph is a clique, except the above examples. So we have the following conjecture.

Conjecture 1.2. Let G be a distance-regular graph of diameter d and height h. If d every pd; h -graph is a clique of size at least 2, then one of the following holds. (1) h ˆ 1 and G is the distance 2-graph of a generalized Odd graph, (2) h ˆ d ÿ 1 and G is the Johnson graph J…3d ÿ 1; d†, (3) h ˆ d and G is the Johnson graph J…3d ‡ 1; d†. In [5], Tomiyama showed that the Johnson graph J…8; 3† is the only distanced regular graph such that 2 ˆ h < d and every pd; 2 -graph is a clique. That means the conjecture is true for 2 ˆ h < d. In this paper, we consider arbitrary height h. The main results in this paper are Theorem 2.1 and Theorem 2.2. The ®rst one shows that the …2d ‡ 1†-gon is the only distance-regular graph with 1 U h < d and d pd; h ˆ 1. The second one shows that the height is equal to either d ÿ 1 or d if d 1 < h and every pd; h -graph is a clique. That gives a partial answer to the above conjecture. 2. De®nition and Results A connected undirected ®nite simple graph G with usual distance qG is said to be distance-regular if the cardinality of the set Pi;t j …x; y† :ˆ fz A G j qG …x; z† ˆ i; qG … y; z† ˆ jg depends only on i; j and t ˆ qG …x; y†. In this case, we write pi;t j :ˆ jPi;t j …x; y†j: The diameter and the height of G are de®ned by d :ˆ maxfqG …x; y† j x; y A Gg and d h :ˆ maxf j j pd; j 0 0g;

respectively. Let t Ct …x; y† :ˆ Ptÿ1; 1 …x; y†;

At …x; y† :ˆ Pt;t 1 …x; y†;

t Bt …x; y† :ˆ Pt‡1; 1 …x; y†

and G t …x† :ˆ Pt;0 t …x; x† ˆ fz A G j qG …x; z† ˆ tg: We denote by ct , at , bt and kt the cardinality of them which depend only on t. The numbers ct , at , bt , kt and pi;t j are called the intersection numbers of G. In particular, we write k ˆ k1 that is called the valency of G.

Distance-regular Graphs of the Height h

419

The following are basic properties of the intersection numbers which we use implicitly in this paper. ci ‡ ai ‡ bi ˆ k. k ˆ b0 V b1 V


V bdÿ2 V bdÿ1 V 1. 1 ˆ c1 U c2 U


U cdÿ1 U cd U k. ci U bj if i ‡ j U d: pi;t j ˆ pj;t i and kt pi;t j ˆ ki pt;i j ˆ kj pt;j i . d d d d d d ci‡1 pi‡1; j ‡ ai pi; j ‡ biÿ1 piÿ1; j ˆ cj‡1 pi; j‡1 ‡ aj pi; j ‡ bjÿ1 pi; jÿ1 . ci‡1


ci‡j bt


bt‡iÿ1 and pi;t i‡t ˆ . (7) pi;i‡j j ˆ c1


cj c1


ci (1) (2) (3) (4) (5) (6)

The reader is referred to [1], [2] for general theory of distance-regular graphs. A graph is called a clique if any two vertices of it are adjacent. We say every pi;t j -graph is a clique if the induced subgraph Pi;t j …x; y† is a clique for any pair of vertices x and y at distance t. So do we for ct , at and bt -graphs. In this paper, we prove the following results. Theorem 2.1. Let G be a distance-regular graph of diameter d and height h. Suppose d pd; h ˆ 1. Then one of the following holds. (1) h ˆ d, (2) h ˆ 1 and G is the …2d ‡ 1†-gon, (3) h ˆ 0 and G is an antipodal 2-cover. Theorem 2.2. Let G be a distance-regular graph of diameter d and height h > 1. d Suppose every pd; h -graph is a clique. Then h A fd ÿ 1; dg. Remarks. Let G be a distance-regular graph of diameter d and height h. d (1) h ˆ 0 i¨ G is an antipodal 2-cover. In this case, pd; 0 ˆ 1. (2) h ˆ 1 i¨ G is the distance 2-graph of a generalized Odd graph. (See [2, §4.2 D].) d In this case, every pd; 1 -graph is a clique of size ad . The Johnson graph J…2d ‡ 1; d† and the halved …2d ‡ 1†-cube are contained in this class. (3) k ˆ 2 i¨ G is either 2d-gon or …2d ‡ 1†-gon that has h ˆ 0 or 1, respectively. d (4) There exists several distance-regular graphs with pd; d ˆ 1. For example, antipodal 3-cover, the Johnson graph J…3d; d† and the Biggs-Smith graph. (5) In [5], Tomiyama showed that J…8; 3† is the only distance-regular graph d such that 2 ˆ h < d and every pd; 2 -graph is a clique. This proves the Theorem 2.2 for the case h ˆ 2.

3. Preliminaries In this section, we collect several results for a distance-regular graph.

420

A. Hiraki

Proposition 3.1. (1) If c2 ˆ c3 , then c3 ˆ 1. (2) If bi ‡ ci‡1 ˆ a1 ‡ 2 for some 2 U i U d ÿ 1, then ci‡1 ˆ 1. (3) If cs‡1 ˆ 1 and b1 > b2 , then b1 > b2 >


> bs . (4) Suppose …csÿ1 ; bsÿ1 † 0 …cs ; bs † ˆ …cs‡tÿ1 ; bs‡tÿ1 † 0 …cs‡t ; bs‡t † with 3 U s. Then t U s ÿ 1. Moreover the following hold. (4-i) If bsÿ1 ˆ bs , then t U s ÿ 2. (4-ii) If bsÿ1 ˆ bs , and cs ˆ cs‡t then t U s ÿ 3. Proof. See [2, Theorem 5.4.1], [2, Corollary 5.5.3], [4, Lemma 2.4] and [3, Proposition 2.3], respectively. r Corollary 3.2. If c3 ˆ c4 and b2 ˆ b3 , then 1 ˆ c3 ˆ c4 and b1 ˆ b2 ˆ b3 . Proof. If c2 < c3 , then we have a contradiction from Proposition 3.1 (4). Hence we have 1 ˆ c2 ˆ c3 from Proposition 3.1 (1). The assertion follows from Proposition 3.1 (3). r Lemma 3.3. Suppose there exist vertices v; x A G such that qG …v; x† ˆ t and t Pt‡s; s …v; x† is a clique. Then bt‡j U csÿj‡1

for all 1 U j U s ÿ 1:

t Proof. Suppose bt‡j > csÿj‡1 for some 1 U j U s ÿ 1. Take u A Pt‡s; s …v; x† and w A s Pjÿ1; sÿj‡1 …x; u†. Then qG …v; w† ˆ t ‡ j ÿ 1. Since bt‡jÿ1 V bt‡j > csÿj‡1 ; we have y t‡j‡1 A Bt‡jÿ1 …v; w† ÿ Csÿj‡1 …u; w†: Take any z A Bt‡j …v; y† and let z 0 A Pt‡s; sÿjÿ1 …v; z†. t‡s t‡s 0 0 t‡s 0 Then z A Pt‡j‡1; sÿjÿ1 …v; z †; y A Pt‡j; sÿj …v; z † and x A Pt; s …v; z †. Since fu; z 0 g J t 0 Pt‡s; s …v; x†, we have qG …u; z † U 1 from our assumption. Thus

…s ÿ j ‡ 1† ÿ 1 ˆ qG …u; w† ÿ qG …w; y† U qG …u; y† U qG …u; z 0 † ‡ qG …z 0 ; y† U 1 ‡ …s ÿ j†: As y B Csÿj‡1 …u; w†, we have qG …u; y† ˆ s ÿ j ‡ 1 and qG …u; z 0 † ˆ 1. Since …s ÿ j ‡ 1† ÿ 1 ˆ qG …u; y† ÿ qG …y; z† U qG …u; z† U qG …u; z 0 † ‡ qG …z 0 ; z† ˆ 1 ‡ …s ÿ j ÿ 1†; we have qG …u; z† ˆ s ÿ j and hence z A Csÿj‡1 …u; y†. This implies Bt‡j …v; y† J r Csÿj‡1 …u; y† which contradicts initial assumption. Lemma 3.4. Suppose bdÿ1 < c2 . Then (1) cdÿ1 < cd . (2) Let u; v; x A G such that v; x A G d …u†, qG …v; x† ˆ t and Ct …v; x† J G d …u†. t Then Ptÿj; j …v; x† J G d …u† for all 1 U j U t ÿ 1.

Distance-regular Graphs of the Height h

421

Proof. (1) Suppose cdÿ1 ˆ cd . Let a; b A G with qG …a; b† ˆ d. Take g A Cd …b; a† and d A Bdÿ1 …g; b†. Note that Cdÿ1 …g; b† ˆ Cd …a; b† since cdÿ1 ˆ cd . We have d A Ad …a; b† J G d …a†. Since b A Cd …g; d† ÿ Cd …a; d†, there exists h A Cd …a; d†ÿCd …g; d†. Note that b B Cdÿ1 …a; h† ˆ Cd …g; h†. We have qG …b; h† ˆ 2. Take any x A C2 …b; h†. Since qG …g; h† ˆ d and qG …h; x† ˆ 1, we have x B Cdÿ1 …g; b† ˆ Cd …a; b†. This implies x A Ad …a; b† J G d …a† and thus C2 …b; h† J Bdÿ1 …a; h† which contradicts our assumption. (2) We prove our assertion by induction on j. The case j ˆ 1 follows from our t assumption. Let 2 U j U t ÿ 1 and y A Ptÿj; j …v; x†. Suppose y B G d …u† and derive a t contradiction. For any z A Cj …x; y†, we have z A Ptÿj‡1; jÿ1 …v; x†. From the inductive assumption, we have z A G d …u† and hence y A G dÿ1 …u†. This implies Cj …x; y† J Bdÿ1 …u; y† which contradicts bdÿ1 < c2 . The lemma is proved. r 4. Distance-regular graphs of height h In this section, we study basic properties for distance-regular graphs of height h. Let G be a distance-regular graph of diameter d and height h with 2 U h < d. Lemma 4.1. (1) pi;d j ˆ 0 if i ‡ j > d ‡ h, (2) pi;d j 0 0 if i ‡ j ˆ d ‡ h. Proof. The case i ˆ d follows from the de®nition of height. Since d d d d d d ci‡1 pi‡1; j ‡ ai pi; j ‡ biÿ1 piÿ1; j ˆ cj‡1 pi; j‡1 ‡ aj pi; j ‡ bjÿ1 pi; jÿ1 ;

the assertions follow by induction on d ÿ i.

r

Lemma 4.2. Let t be an integer with h U t U d. Let a; b A G with qG …a; b† ˆ t. For t t any g A Pd; dÿt …a; b† and any d A Pd; d‡hÿt …a; b†, the following hold. (1) qG …g; d† ˆ h, t d t d (2) h 0 Pd; d‡hÿt …a; b† J Pd; h …a; g† and 0 < pd; d‡hÿt U pd; h , t d t d (3) h 0 Pd; dÿt …a; b† J Pd; h …a; d† and 0 < pd; dÿt U pd; h . Proof. (1) Since d; g A G d …a†, we have h V qG …g; d† V qG …b; d† ÿ qG …b; g† ˆ …d ‡ h ÿ t† ÿ …d ÿ t† ˆ h: This is the desired result. (2), (3) These are direct consequences of (1) and Lemma 4.1 (2).

r

d Lemma 4.3. Let u; v A G with qG …u; v† ˆ d and y A Pdÿi; h‡i …u; v† with 1 U i U d ÿ h.

(1) Bdÿi …u; y† J Ch‡i …v; y† and bdÿi U ch‡i . (2) jAdÿi …u; y† V Ah‡i …v; y†j ˆ jCdÿi …u; y† V Ch‡i …v; y†j ‡ adÿi ‡ bdÿi ÿ ch‡i . d Proof. (1) By Lemma 4.1, we have Bdÿi …u; y† V Bh‡i …v; y† J Pdÿi‡1; h‡i‡1 …u; v† ˆ h d and Bdÿi …u; y† V Ah‡i …v; y† J Pdÿi‡1; h‡i …u; v† ˆ h. The assertion follows.

422

A. Hiraki

d (2) Let A :ˆ Adÿi …u; y† and C :ˆ Ch‡i …v; y†. Since Pdÿi; h‡i‡1 …u; v† ˆ h, we have

A ˆ …A V C† U …A V Ah‡i …v; y†† U …A V Bh‡i …v; y†† ˆ …A V C† U …A V Ah‡i …v; y†† U h and

C ˆ …Cdÿi …u; y† V C† U …A V C† U …Bdÿi …u; y† V C† ˆ …Cdÿi …u; y† V C† U …A V C† U Bdÿi …u; y†

from (1). Hence adÿi ˆ jAj ˆ jA V Ah‡i …v; y†j ‡ jA V Cj; ch‡i ˆ jCj ˆ jCdÿi …u; y† V Cj ‡ jA V Cj ‡ bdÿi : We obtain the desired result.

r

Lemma 4.4. Suppose there exist vertices u; v A G such that qG …u; v† ˆ d and d Pd; h …u; v† is a clique. Then for h U t U d, the following hold. d d (1) qG …x; y† V d ‡ h ÿ t ÿ 1 for any x A Pd; h …u; v† and any y A Pt; dÿt …u; v† d d (2) qG …x; w† U d ÿ t ‡ 1 for any x A Pd; h …u; v† and any w A Pt; d‡hÿt …u; v† (3) cdÿjÿ1 U bh‡j for all 0 U j U d ÿ h ÿ 2. t t d Proof. (1) Since v A Pd; dÿt …u; y†, there exists z1 A Pd; d‡hÿt …u; y† J Pd; h …u; v† from Lemma 4.2 (2). Thus

d ‡ h ÿ t ˆ qG …z1 ; y† U qG …z1 ; x† ‡ qG …x; y† U 1 ‡ qG …x; y† d as z1 ; x A Pd; h …u; v†. t d (2) Lemma 4.2 (3) implies that there exists z2 A Pd; dÿt …u; w† J Pd; h …u; v† since t v A Pd; d‡hÿt …u; w†. The assertion follows from

qG …w; x† U qG …w; z2 † ‡ qG …z2 ; x† U …d ÿ t† ‡ 1: d (3) Suppose cdÿjÿ1 > bh‡j for some 0 U j U d ÿ h ÿ 2. Let d A Pdÿj; j …u; v†. dÿj dÿj d Since v A Pd; j …u; d†, there exists x A Pd; h‡j …u; d† J Pd; h …u; v† from Lemma 4.2 (2). Then there exists y A Cdÿj …u; d† ÿ Bh‡j …x; d† since cdÿj V cdÿjÿ1 > bh‡j . Take any z A Cdÿjÿ1 …u; y† and let d z 0 A Ph;dÿjÿ2 dÿhÿjÿ2 …u; z† J Ph; dÿh …u; v† V G dÿhÿjÿ1 …y†: d 0 Since x A Pd; h …u; v†, we have qG …x; z † V d ÿ 1 from (1). Hence

…h ‡ j† ‡ 1 V qG …x; d† ‡ qG …d; y† V qG …x; y† V qG …x; z 0 † ÿ qG …z 0 ; y† V …d ÿ 1† ÿ …d ÿ h ÿ j ÿ 1† ˆh‡ j

Distance-regular Graphs of the Height h

423

and thus qG …x; y† ˆ h ‡ j as y B Bh‡j …x; d†. Since …h ‡ j† ‡ 1 ˆ qG …x; y† ‡ qG … y; z† V qG …x; z† V qG …x; z 0 † ÿ qG …z 0 ; z† V …d ÿ 1† ÿ …d ÿ h ÿ j ÿ 2† ˆ h ‡ j ‡ 1; we obtain qG …x; z† ˆ h ‡ j ‡ 1 and hence z A Bh‡j …x; y†. This implies Cdÿjÿ1 …u; y† J Bh‡j …x; y† which contradicts initial assumption. r

5. Some Inequalities of Intersection Numbers In this section, we assume G is a distance-regular graph of diameter d, height h d with 1 < h U d ÿ 1 and every pd; h -graph is a clique. d d Lemma 5.1. Let u; v A G with qG …u; v† ˆ d, x A Pd; h …u; v† and y A Pdÿi;h‡i …u; v† with 0 U i U d ÿ h:

(1) (2) (3) (4) (5) (6) (7)

cdÿjÿ1 U bh‡j for 0 U j U d ÿ h ÿ 2. bh‡j U cdÿhÿj‡1 for 1 U j U d ÿ h ÿ 1. Cdÿi …u; y† V Ch‡i …v; y† ˆ h. d d Ad …u; x† U fxg ˆ Ch …v; x† U Pd; h …u; v† and ad ‡ 1 ˆ ch ‡ pd; h . qG …x; y† U i ‡ 1. qG …x; z† U i for any z A Bdÿi …u; y†. If qG …x; y† ˆ i V 2, then Adÿi …u; y† V Ah‡i …v; y† J Ai …x; y†.

Proof. (1) This follows from Lemma 4.4 (3). h h d (2) As u A Pd; d …v; x†, we have Pd; dÿh …v; x† J Pd; h …v; u† from Lemma 4.2 (3). h Thus Pd; dÿh …v; x† is a clique. The assertion is a direct consequence of Lemma 3.3. dÿi (3) By replacing u and v, we may assume i 0 d ÿ h. Since v A Pd; h‡i …u; y†, 0 dÿi d there exists v A Pd; i …u; y† J Pd; h …u; v† from Lemma 4.2 (3). Take any d A d 0 d 0 Cdÿi …u; y†. Since v A Pd; h …u; v † and d A Pdÿiÿ1;i‡1 …u; v †, Lemma 4.4 (1) implies qG …v; d† V h ‡ i. Thus we have d B Ch‡i …v; y†. d (4) Since Pd; h …u; v† is a clique, we have the assertion from (3). (5) The desired result follows from Lemma 4.4 (2). d (6) By Lemma 4.3 (1), z A Pdÿi‡1; h‡iÿ1 …u; v†. The assertion follows from (5). d (7) Take any w A Adÿi …u; y† V Ah‡i …v; y† J Pdÿi; h‡i …u; v†. From (5), we have i ‡ 1 V qG …x; w† V qG …u; x† ÿ qG …u; w† ˆ i: To prove the lemma we assume qG …x; w† ˆ i ‡ 1 and get a contradiction. For any z A Bdÿi …u; w†, we have …i ‡ 1† ÿ 1 ˆ qG …x; w† ÿ qG …w; z† U qG …x; z† U i

424

A. Hiraki

from (6). So qG …x; z† ˆ i and Bdÿi …u; w† U fyg J Ci‡1 …x; w†. This implies bdÿi < ci‡1 . On the other hand we obtain ch‡iÿ1 U bdÿi from (1). This is a contradiction. r Lemma 5.2. Suppose 1 < h U d ÿ 2. Then d h (1) pd; h ˆ pd; dÿh (2) bi U ch‡i ‡ cdÿi ÿ bdÿi for all 2 U i U d ÿ h. d Proof. Let u; v A G with qG …u; v† ˆ d and x A Pd; h …u; v†. h h d (1) Since u A Pd; d …v; x†, there exists y A Pd; dÿh …v; x† J Pd; h …v; u† from Lemma d d 4.2 (3). For any z A Pd; h …v; u† ÿ fyg, we have z A Ah …u; y† V Ad …v; y† as Pd; h …v; u† d is a clique. From Lemma 5.1 (7), z A Adÿh …x; y†. This implies that Pd; h …v; u† J h h d Pd; dÿh …v; x†. Since pd; dÿh U pd; h from Lemma 4.2 (3), the assertion follows. d dÿi (2) Let 2 U i U d ÿ h and take y A Pdÿi; h‡i …u; v†. Since v A Pd; h‡i …u; y†, there 0 dÿi d 0 exist x A Pd; i …u; y† J Pd; h …u; v† from Lemma 4.2 (3). Since qG …x ; y† ˆ i V 2, we have

Bdÿi …u; y† U …Adÿi …u; y† V Ah‡i …v; y†† J Ai …x 0 ; y† U Ci …x 0 ; y† by Lemma 5.1 (6) (7). Therefore we obtain bdÿi ‡ …adÿi ‡ bdÿi ÿ ch‡i † U ai ‡ ci from lemma 4.3 (2) and Lemma 5.1 (3). The lemma is proved.

r

Proposition 5.3. There exist no distance-regular graphs of diameter d, height h with d 3 U h U d ÿ 3 and every pd; h -graph is a clique. Proof. Since 3 U h U d ÿ 3, we have cdÿjÿ1 ˆ bh‡j ˆ cdÿhÿj‡1 for 1 U j U d ÿ h ÿ 2 from Lemma 5.1 (1), (2). In particular, c3 ˆ c4 ˆ


ˆ cdÿ2 ˆ bh‡1 ˆ


ˆ bdÿ2 : By Lemma 5.2 (2) and Lemma 5.1 (1), b2 U ch‡2 ‡ cdÿ2 ÿ bdÿ2 ˆ ch‡2 U cdÿ1 U bh : Hence ch‡2 ˆ cdÿ1 ˆ bh ˆ b2 . From Corollary 3.2, we have b1 ˆ b2 ˆ b3 ˆ


ˆ bh ˆ cdÿ1 and

1 ˆ c2 ˆ


ˆ cdÿ2 ˆ bh‡1 ˆ


ˆ bdÿ1 :

From Lemma 5.1 (4) and Lemma 5.2 (1), we have d h ad ˆ pd; h ˆ pd; dÿh ˆ

bh bh‡1


bdÿ1 ˆ bh ˆ b1 ˆ cdÿ1 : c1 c2


cdÿh

Hence we obtain cd ˆ k ÿ ad ˆ k ÿ b1 ˆ a1 ‡ 1 and bdÿ1 ‡ cd ˆ a1 ‡ 2. From Lemma 3.1 (2), we have cd ˆ 1 and thus

Distance-regular Graphs of the Height h

425

k ˆ ad ‡ cd ˆ cdÿ1 ‡ cd U 2cd ˆ 2: Hence G is an ordinary polygon which contradicts h V 3. The assertion follows. r

6. The Case h ˆ d ÿ 2 In this section, we assume that G denotes a distance-regular graph of diameter d, d height h ˆ d ÿ 2 V 3 and every pd; dÿ2 -graph is a clique. From Lemma 5.1 (1) (2), we have bdÿ2 V cdÿ1 and bdÿ1 U c2 . Fix u; v A G with qG …u; v† ˆ d and set Pi; j ˆ Pi;d j …u; v†. Lemma 6.1. Let x A Pd; dÿ2 and z A Pdÿ2; dÿ1 . Suppose bdÿ2 > cdÿ1 . Then (1) G 2 …z† V Pd; dÿ2 0 h and qG …x; z† U 3. (2) qG …x; w† U 3 for any w A Bdÿ2 …u; z†. Proof. Since bdÿ2 > cdÿ1 , there exists z1 A Bdÿ2 …u; z† ÿ Cdÿ1 …v; z†. Let z2 A Bdÿ1 …u; z1 †. As Pdÿ1;d ˆ h, we have z1 A Pdÿ1; dÿ1 and thus z2 A Cdÿ1 …v; z1 † from Lemma 4.3 (1). Hence qG …x; z† U 1 as fx; z2 g J Pd; dÿ2 . This implies qG …x; z† U qG …x; z2 † ‡ qG …z2 ; z† U 1 ‡ 2: The assertion (1) follows. Let w A Bdÿ2 …u; z†. Take w2 A Bdÿ1 …u; w† and y A dÿ2 dÿ2 d Pd; d …u; z†. Then fz2 ; w2 g J Pd; 2 …u; z† J Pd; dÿ2 …u; y† from Lemma 4.2 (3). Hence z2 and w2 are adjacent and qG …x; w† U qG …x; z2 † ‡ qG …z2 ; w2 † ‡ qG …w2 ; w† ˆ 3: This is the desired result.

r

Lemma 6.2. bdÿ2 ˆ cdÿ1 . Proof. We assume bdÿ2 > cdÿ1 and derive a contradiction. Note that b2 V b3 V bdÿ2 > cdÿ1 V cdÿ2 . Let x A Pd; dÿ2 . Then Pdÿ2; d ˆ d dÿ2 Pd; dÿ2 …v; u† ˆ Pd; 2 …v; x† J G 2 …x† from Lemma 4.2 (3) and Lemma 5.2 (1). Take y A Pdÿ2; d . Then there exists z A B2 …x; y† ÿ Cdÿ2 …u; y†. If z A Bdÿ2 …u; y†, then Lemma 5.1 (6) implies qG …x; z† U 2 contradicting z A B2 …x; y†. Thus z A Adÿ2 …u; y†. As Pdÿ2; d J G 2 …x†, we have z A Pdÿ2;dÿ1 . We can take w A B3 …x; z† ÿ Cdÿ2 …u; z† as b3 > cdÿ2 . We show qG …u; w† ˆ qG …v; w† ˆ d ÿ 2. From Lemma 6.1 (2), B3 …x; z† V Bdÿ2 …u; z† ˆ h and hence w A Adÿ2 …u; z†. If qG …v; w† V d ÿ 1, then w A Pdÿ2; dÿ1 as Pdÿ2; d J G 2 …x†. This contradict Lemma 6.1 (1). Therefore we have qG …u; w† ˆ qG …v; w† ˆ d ÿ 2. d d Then we have w A Pdÿ2; 2 …v; y† and u A Pd; dÿ2 …v; y†. Lemma 4.4 (1) implies r qG …u; w† V d ÿ 1. This is a contradiction. The lemma is proved. Lemma 6.3. Let y A Pdÿ1; dÿ1 and z A Pdÿ2; 2 . If bdÿ1 < c2 , then the following hold. (1) There exists g1 A G d …z† V Pd; dÿ2 : (2) There exists g2 A G d …z† V Pdÿ2; d :

426

A. Hiraki

(3) qG …z; y† V d ÿ 1. (4) qG …y; w† V d ÿ 1 for any w A Cd …u; v†. dÿ2 d Proof. (1) From Lemma 4.2 (2), there exists g1 A Pd; d …u; z† J Pd; dÿ2 …u; v† ˆ Pd; dÿ2 . 0 d (2) Let z 0 A P2;dÿ2 dÿ4 …u; z† J P2; dÿ2 . There exists g2 A G d …z † V Pd; dÿ2 …v; u† 0 0 similar to (1). Note that qG …g2 ; v† ˆ qG …g2 ; z † ˆ d, qG …v; z † ˆ d ÿ 2 and z A 0 0 P2;dÿ2 dÿ4 …v; z †. From Lemma 5.1 (3), we have Cdÿ2 …v; z † J G d …g2 †. As bdÿ1 < c2 from our assumption, we apply Lemma 3.4 (2) and obtain z A G d …g2 †. Hence g2 A G d …z† V Pdÿ2;d . (3) Let g1 ; g2 as in (1), (2). Then it is clear that g1 and g2 are not adjacent. Suppose qG …z; y† U d ÿ 2. Then Lemma 5.1 (5) implies

d ˆ qG …z; g1 † U qG …z; y† ‡ qG …y; g1 † U …d ÿ 2† ‡ 2: Thus qG …z; y† ˆ d ÿ 2 and qG …y; g1 † ˆ 2. Similarly, qG … y; g2 † ˆ 2. From Lemma 4.2 (3), dÿ2 d fg1 ; g2 g J Pd; 2 …z; y† J Pd; dÿ2 …z; d† dÿ2 where d A Pd; d …z; y†. This contradicts g1 and g2 are not adjacent. (4) Suppose qG …y; w† U d ÿ 2 for some w A Cd …u; v†. Since qG …y; v† ˆ d ÿ 1, we have qG …y; w† ˆ d ÿ 2. Note that Cdÿ1 …u; w† J Pdÿ2; 2 . From (3), we have

fvg U Cdÿ1 …u; w† J Bdÿ2 …y; w†: which contradicts Lemma 6.2. The lemma is proved.

r

Lemma 6.4. (1) bdÿ1 ˆ c2 , (2) adÿ1 ‡ 1 U cdÿ1 . Proof. (1) We assume bdÿ1 < c2 and derive a contradiction. Let x A Pd; dÿ2 . By Lemma 3.4 (1) and Lemma 6.2, we have cd > cdÿ1 ˆ bdÿ2 and thus there exists w A Cd …u; v† ÿ Bdÿ2 …x; v†. Since Cd …u; v† V Cdÿ2 …x; v† ˆ h from Lemma 5.1 (3), we have w A Adÿ2 …x; v†. Let z A Cdÿ1 …u; w† J Pdÿ2; 2 and z 0 A G d …z† V Pd; dÿ2 as Lemma 6.3 (1). Since x; z 0 A Pd; dÿ2 , we have d ˆ qG …z 0 ; z† U qG …z 0 ; x† ‡ qG …x; z† U qG …z 0 ; x† ‡ qG …x; w† ‡ qG …w; z† U 1 ‡ …d ÿ 2† ‡ 1 ˆ d: 0

This implies qG …z ; x† ˆ 1; qG …x; z† ˆ d ÿ 1; qG …x; w† ˆ d ÿ 2 and qG …z 0 ; w† ˆ d ÿ 1: Since Bdÿ2 …v; x† J Pdÿ1; dÿ1 from Lemma 4.3 (1), it follows from Lemma 6.3 (4) that fz 0 g U Bdÿ2 …v; x† J Bdÿ2 …w; x†: This is a contradiction.

Distance-regular Graphs of the Height h

427

(2) Let y A Pdÿ1;dÿ1 and Y ˆ Adÿ1 …u; y† V Adÿ1 …v; y†. Take x A Bdÿ1 …u; y† and x 0 A Bdÿ1 …v; y† Then x A Pd; dÿ2 and x 0 A Pdÿ2; d from Lemma 4.3 (1). We show that Y U f yg J C2 …x; x 0 †. Suppose there exists z A Y ÿ G 1 …x†. As fxg U Bdÿ1 …u; z† J Pd; dÿ2 from Lemma 4.3 (1), we have Bdÿ1 …u; z† J G 1 …x† as Pd; dÿ2 is a clique. Thus Bdÿ1 …u; z† U fyg J C2 …z; x† which contradicts (1). Hence Y J G 1 …x†. By symmetry, we obtain Y J G 1 …x 0 †. Whence this implies Y U fyg J C2 …x; x 0 † and …adÿ1 ‡ bdÿ1 ÿ cdÿ1 † ‡ 1 ˆ jY j ‡ jfygj U c2 ˆ bdÿ1 from (1), Lemma 4.3 (2) and Lemma 5.1 (3). This is the desired result.

r

7. Proof of Theorems In this section, we prove our results. Proof of Theorem 2.1. We may assume h 0 0; d and show that (2) holds. From Lemma 4.2 (3), we have 2 h h d d ph;d dÿh pd; d ˆ pd; dÿh pd; h U … pd; h † ˆ 1 h and hence ph;d dÿh ˆ pd; d ˆ 1. Note that cd cdÿ1


cdÿh‡1 ˆ ph;d dÿh ˆ 1: cd U c1 c2


ch d d Since pd; h ˆ 1, every pd; h -graph is a clique. From Lemma 5.1 (4), ad ˆ ch U cd . Hence we have k ˆ ad ‡ cd U 2. Therefore G is the …2d ‡ 1†-gon and (2) holds. r

Proof of Theorem 2.2. The case h ˆ 2 has already proved by Tomiyama in [5]. To prove the theorem, it is su½cient to show that there exist no distance-regular d graphs of diameter d, height h ˆ d ÿ 2 V 3 and every pd; h -graph is a clique by Proposition 5.3. Suppose there exists such a distance-regular graph G. Then Lemma 5.2 (1), Lemma 5.1 (4), Lemma 6.2 and Lemma 6.4 imply bdÿ1 ˆ c2 ; bdÿ2 ˆ cdÿ1 , d dÿ2 pd; dÿ2 ˆ pd; 2 ˆ

bdÿ2 bdÿ1 ˆ bdÿ2 c2

and

ad ‡ 1 ˆ cdÿ2 ‡ bdÿ2 :

We have bdÿ1 U b2 U cd ‡ cdÿ2 ÿ bdÿ2 ˆ cd ‡ …ad ‡ 1 ÿ bdÿ2 † ÿ bdÿ2 ˆ k ‡ 1 ÿ 2cdÿ1 ˆ …bdÿ1 ‡ adÿ1 ‡ cdÿ1 † ‡ 1 ÿ 2cdÿ1 ˆ …adÿ1 ÿ cdÿ1 ‡ 1† ‡ bdÿ1 U bdÿ1

428

A. Hiraki

from Lemma 5.2 (2) and Lemma 6.4 (2). Hence bdÿ1 ˆ bdÿ2 ˆ


ˆ b2

and

adÿ1 ˆ cdÿ1 ÿ 1:

Since bdÿ1 ˆ c2 U cdÿ1 ˆ bdÿ2 ˆ bdÿ1 ; we have 1 ˆ c2 ˆ c3 ˆ


ˆ cdÿ1 ˆ bdÿ1 : from Lemma 3.1 (1). So we have k ˆ cdÿ1 ‡ adÿ1 ‡ bdÿ1 ˆ cdÿ1 ‡ …cdÿ1 ÿ 1† ‡ bdÿ1 ˆ 2: This contradicts 3 U h. The theorem is proved.

r

References 1. Bannai, E., Ito, T.: Algebraic Combinatorics I, Benjamin-Cummings, California (1984) 2. Brouwer, A. E., Cohen, A. M., Neumaier, A.: Distance-Regular Graphs, Springer Verlag, Berlin, Heidelberg (1989) 3. Hiraki, A., Suzuki, H., Wajima, M.: On distance-regular graphs with ki ˆ kj , II, Graphs Comb. 11, 305±317 (1995) 4. Hiraki, A.: Distance-regular subgraphs in a distance-regular graph, III, Eur. J. Comb. 17, 629±636 (1996) 5. Tomiyama, M.: On distance-regular graphs with height two, J. Algebraic Comb. 5, 57± 76 (1996)

Received: January 8, 1997 Revised: November 30, 1998