On Application of the Retracing Method for Distance- Regular Graph

ABSTRACT

This paper is an exposition of the article written by Hiraki entitled Applications of Retracing Methods for Distance-Regular Graphs published in European Journal of Combinatorics, April 2004. The main results of the article are as follows:

Theorem 1.1 Let Γ be a distance-regular graph of the d with

r = ǀ {I ǀ (c₁, a₁, b₁) = ( c₁, a₁, b₁)} ǀ≥2

and c_{r +1}≥2. Let m, s and t be positive integers with s≤m, m+t≤d and (s,t) ≠(1,1).

Suppose b_m-s+1= ∙∙∙ = b_m = 1 + b_{m +1}, c_{m + 1}= ∙∙∙ = 1 + c_m and a_{m – s + 2} = ∙∙∙ = a_{m + t – 1} = 0. Then the following hold.

• If b_{m + 1} ≥ 2, then t ≤ r – 2.
• If c_m ≥ 2, then s ≤ r – 2.

Corollary 1.2 Under the assumption of Theorem 1.1, the following hold.

• If r = t and b_{m + 1} ≥ 2, then s ≤ 2.
• If r = s and c_m ≥ 2, then t ≤ 2.

Corollary 1.3 Let Γ be a distance-regular graph of valency k ≥ 3 with

• If k ≥ 4, then t ≤ r – 2.
• If 2 ≤ t = r, then Γ is either the Odd graph, or the doubled Odd graph.
• If 2 ≤ t = r – 1, then Γ is the Foster graph.