Akira Hiraki

In this paper we study a distance-regular graph Γ of diameter d ≥ 3 which satisfies the following two conditions: (a) For any integer i with 1 ≤ i ≤ d - 1 and for any pair of vertices at distance i in Γ there exists a strongly closed subgraph of diameter i containing them (b) There exists a strongly closed subgraph Δ which is completely regular in Γ. It is known that if Δ has diameter 1, then Γ is a regular near polygon. We prove that if a strongly closed subgraph Δ of diameter j with 2 ≤ j ≤ d - 1 is completely regular of covering radius d - j in Γ, then Γ is either a Hamming graph or a dual polar graph. © 2011 Springer.

Let Gamma be a Delsarte set graph with an intersection number c(2) (i.e., a distance-regular graph with a set C of Delsarte cliques such that each edge lies in a positive constant number n(C) of Delsarte cliques in C). We showed in Bang et al. (J Combin 28:501-506, 2007) that if psi(1) > 1 then c(2) >= 2 psi(1) where psi(1) := vertical bar Gamma(1)(x)boolean AND C vertical bar for x is an element of V(Gamma) and C aDelsarte clique satisfying d(x, C) = 1. In this paper, we classify Gamma with the case c(2) = 2 psi(1) > 2. As a consequence of this result, we show that if c(2) <= 5 and psi(1) > 1 then Gamma is either a Johnson graph or a folded Johnson graph (J) over bar (4s, 2s) with s >= 3.

In this paper we study a distance-regular graph Gamma of diameter d >= 4 such that for any given pair of vertices at distance d - 1 there exists a strongly closed subgraph of diameter d - 1 containing them. We prove several inequalities for intersection numbers of Gamma. We show that if the equalities hold in some of these inequalities, then Gamma is either the Odd graph, the doubled Odd graph, the doubled Grassmann graph, the Hamming graph or the dual polar graph. (C) 2008 Elsevier Ltd. All rights reserved.

Let Gamma be a distance-regular graph of diameter d >= 3 with c(2) > 1. Let m be an integer with 1 <= m <= d - 1. We consider the following conditions: (SC)(m) : For any pair of vertices at distance m there exists a strongly closed subgraph of diameter m containing them. (BB)(m) : Let(x, y, z) be a triple of vertices with partial derivative(Gamma)(x, y) = 1 and partial derivative(Gamma)(x, z) = partial derivative(Gamma)(y, z) = m. Then B(x, z) = B(y, z). (CA)(m) : Let (x, y, z) be a triple of vertices with partial derivative(Gamma)(x, y) = 2, partial derivative(Gamma)(x, z) = partial derivative(Gamma)(y, z) = m and vertical bar C(z, x) boolean AND C(z, y)vertical bar >= 2. Then C(x, z) boolean OR A(x, z) = C(y, z) boolean OR A(y, z). In [12] we have shown that the condition (SC)(m) holds if and only if both of the conditions (BB)(i) and (CA)(i) hold for i = 1, ..., m. In this paper we show that if a(1) = 0 < a(2) and the condition (BB)(i) holds for i = 1, ..., m, then the condition (CA)(i) holds for i = 1, ..., m. In particular, the condition (SC)(m) holds. Applying this result we prove that a distance-regular graph with classical parameters (d, b, alpha, beta) such that c(2) > 1 and a(1) = 0 < a(2) satisfies the condition (SC)(i) for i = 1, ..., d - 1. In particular, either (b, alpha, beta) = (-2, -3, -1 - (-2)(d)) or (b, alpha, beta) = (-3, -2, -1+(-3)(d)/2) holds.

Let Gamma be a distance-regular graph of diameter d >= 3 with c(2) > 1. Let m be an integer with 1 <= m <= d - 1. We consider the following conditions: (SC)(m) : For any pair of vertices at distance m there exists a strongly closed subgraph of diameter m containing them. (BB)(m) : Let (x, y, z) be a triple of vertices with partial derivative(Gamma) (x, y) = 1 and partial derivative(Gamma) (x, z) = partial derivative(Gamma) (y, z) = m. Then B(x, z) = B(y, z). (CA)(m) : Let (x, y, z) be a triple of vertices with partial derivative(Gamma) (x, y) = 2, partial derivative(Gamma) (x, z) = partial derivative(Gamma) (y, z) = m and |C(z, x) boolean AND C(z, y)| >= 2. Then C(x, z) boolean OR A(x, z) = C(y, z) boolean OR A(y, z). Suppose that the condition (SC)(m) holds. Then it has been known that the condition (BB)(i) holds for all i with 1 <= i <= m. Similarly we can show that the condition (CA)(i) holds for all i with 1 <= i <= m. In this paper we prove that if the conditions (BB)(i) and (CA)(i) hold for all i with 1 <= i <= m, then the condition (SC)(m) holds. Applying this result we give a sufficient condition for the existence of a dual polar graph as a strongly closed subgraph in Gamma.

The Hamming graph H (d, q) satisfies the following conditions: (i)For any pair (u, v) of vertices there exists a strongly closed subgraph containing them whose diameter is the distance between u and v. In particular, any strongly closed subgraph is distance-regular.(ii)For any pair (x, y) of vertices at distance d - 1 the subgraph induced by the neighbors of y at distance d from x is a clique of size a1 + 1. In this paper we prove that a distance-regular graph which satisfies these conditions is a Hamming graph. © 2007 Elsevier Ltd. All rights reserved.

In this paper, we consider the class of Delsarte clique graphs, i.e. the class of distance-regular graphs with the property that each edge lies in a constant number of Delsarte cliques. There are many examples of Delsarte clique graphs such as the Hamming graphs, the Johnson graphs and the Grassmann graphs. Our main result is that, under mild conditions, for given s >= 2 there are finitely many Delsarte clique graphs which contain Delsarte cliques with size s + I. Further we classify the Delsarte clique graphs with small s. (c) 2005 Elsevier Ltd. All rights reserved.

We show several inequalities for intersection numbers of distance-regular graphs. As an application of them we characterize the Odd graphs and the doubled Odd graphs with a few of their intersection numbers. In particular, we prove that the diameter d of a bipartite distance-regular graph of valency k and girth 2r + 2 >= 6 is bounded by d <= [k+2/2]r + 1 if it is not the doubled Odd 2 graph. (c) 2006 Published by Elsevier Ltd.

In the previous paper (J. Combin. Theory Ser. B 79 (2000) 211) we introduced the retracing method for distance-regular graphs and gave some applications. In this paper, we give other applications of this method. In particular, we prove the following result: In the previous paper (J. Combin. Theory Ser. B 79 (2000) 211) we introduced the retracing method for distance-regular graphs and gave some applications. In this paper, we give other applications of this method. In particular, we prove the following result: theorem. Let Gamma be a distance-regular graph of diameter d with r = \{i\ (c(i), a(i), b(i)) = (c(1), a(1), b(1))}\ >= 2 and c(r+1) >= 2. Let m, s and t be positive integers with s <= m, m + t <= d and (s, t) not equal (1, 1). Suppose b(m-s+1) = ... = b(m) ... = 1 +b(m+1),c(m+1) = ... = c(m+t) = 1 + c(m) and a(m-s+2) = ... = a(m+t-1) = 0. Then the following hold. (1) If b(m+1) >= 2, then t <= r -2[s/3]. (2) If c(m) >= 2, then s <= r - 2[t/3]. (c) 2004 Elsevier Ltd. All rights reserved.

Brouwer and Wilbrink showed that t + 1 less than or equal to (s(2) + 1)c(d-1) holds for a regular near 2d-gon of order (s, t) with s greater than or equal to 2 and where the diameter d is even. In this note we generalize their inequality to all diameter. (C) 2004 Elsevier Inc. All rights reserved.

Let Gamma be a regular near polygon of order (s, t) with s > 1 and t greater than or equal to 3. Let d be the diameter of Gamma, and let r : = max{i\ (c(i); a(i); b(i)) = (c(1); a(1); b(1))}: In this note we prove several inequalities for Gamma. In particular, we show that s is bounded from above by function in t if d < 3/2 (r + 1). We also consider regular near polygons of order (s, 3).

Let Gamma be a distance-regular graph of diameter d, and t be an integer with 2 less than or equal to t less than or equal to d - 1 such that a(t-1) = 0. For any pair (u, v) of vertices, let Pi(u, v) be the subgraph induced by the vertices lying on shortest paths between u and v. We prove that if Pi(u, v) is a bipartite geodetically closed subgraph for some pair (u, v) of vertices at distance t, then Pi(x, y) is,a bipartite geodetically closed subgraph for any pair (x y) of vertices at distance less than or equal to t. In particular, Pi(x, y) is either a path, an ordinary polygon, a hyper cube or a projective incidence graph. (C) 2003 Elsevier Science Ltd. All rights reserved.

We characterize the doubled Grassmann graphs, the doubled Odd graphs, and the Odd graphs by the existence of sequences of strongly closed subgraphs. (C) 2003 Elsevier Science Ltd. All rights reserved.

In this paper we consider the number t of columns (1, k - 2, 1) in the intersection array of a distance-regular graph. We prove that t is at most one if k greater than or equal to 58.

Let Gamma be a distance-regular graph of diameter d, valency k and r := max{i \ (c,b) = (c(i),b(i))}. Let q be an integer with r + 1 less than or equal to q less than or equal to d - 1. In this paper we prove the following results: Theorem 1 Suppose for any pair of vertices at distance q there exists a strongly closed subgraph of diameter q containing them. Then for any integer i with 1 less than or equal to i less than or equal to q and for any pair of vertices at distance i there exists a strongly closed subgraph of diameter i containing them. Theorem 2 If r greater than or equal to 2, then c(2r+3) not equal 1. As a corollary of Theorem 2 we have d less than or equal to k(2)(r + 1) if r greater than or equal to 2.

We introduce the retracing argument for distance-regular graphs and prove several results by applying this argument. (C) 2000 Academic Press.

We give a complete classification of distance-regular graphs of valency 6 and a(1) = 1.

Let Gamma be a distance-regular,graph with (c(1), b(1)) =... = (c(r), b(r)) not equal (c(r+1) , b(r+1)) =... = (c(2r), b(2r)) where r greater than or equal to 2 and c(r+1) > 1. We prove that r = 2 except for the case a(1) = a(r+1) = 0 and c(r+1) = 2 by showing the existence of strongly closed subgraphs. (C) 1999 Academic Press.

The height of a distance-regular graph of the diameter d is defined by h = max{j | pd,j d ≠ 0}. We show that if Γ is a distance-regular graph of diameter d, height h &gt 1 and every pd,h d-graph is a clique, then h ∈ {d - 1, d}. © Springer-Verlag 1999.

In this paper we show that a regular thick near polygon has a tower of regular thick near sub-polygons as strongly closed subgraphs if the diameter d is greater than the numerical girth g. © 1999 Academic Press.

In this paper we give a sufficient condition for the existence of a strongly closed subgraph which is (c(q) + a(q))-regular of diameter q containing a given pair of vertices at distance q in a distance-regular graph. Moreover we show that a distance-regular graph with r = max{j \ (c(j), a(j), b(j)) = (c(1), a(1), b(1) )}, bq-1 > b(q) and c(q+r) = 1 satisfies our sufficient condition. (C) 1998 Academic Press.

Let Gamma be a distance-regular graph without induced subgraphs K-2,K-1,K-1 and r = max{j \ (c(j), a(j), b(j)) = (c(1), a(1), b(1))}. We give a necessary and sufficient condition for the existence of a strongly closed subgraph which is (c(r+1) + a(r+1))-regular of diameter r + 1 containing a given pair of vertices at distance r + 1. (C) 1998 Academic Press Limited.

We show that a distance-regular graph of valency k > 2 is antipodal, if b(2) = 1. This answers Problem (i) on p. 182 of Brouwer, Cohen and Neumaier [4]. (C) 1997 Academic Press Limited.

We show that the number of columns (1, k - 2, 1) in the intersection array of distance-regular graphs is at most 20. © Springer-Verlag 1996.

Let Γ be a distance-regular graph with l(1, a1, b1) = 1 and cs+1 = 1 for some positive integer s. We show the existence of a certain distance-regular graph of diameter s, containing given two vertices at distance s, as a subgraph in Γ. © 1996 Academic Press Limited.

Let G{cyrillic} be a distance-regular graph of diameter d and i-th valency ki. We show that if k2 = kj for 2 +j ≥ d and 2 &lt j, then G{cyrillic} is a polygon (k = 2) or an antipodal 2-cover (kd = 1). We also give a short proof of Terwilliger's inequality for bipartite distance-regular graphs and a refinement of Ivanov's argument on diameter bound. © 1995 Springer-Verlag.