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

Suzuki, Hiroshi

Journal of Algebraic Combinatorics, Tome 30 (2009) no. 3, pp. 401-413.

Résumé

Summary: Let $\Gamma =( X, R)$ be a distance-regular graph of diameter $d$. A $parallelogram$ of length $i$ is a 4-tuple $xyzw$ consisting of vertices of $\Gamma $such that $\partial ( x, y)= \partial ( z, w)=1, \partial ( x, z)= i$, and $\partial ( x, w)= \partial ( y, w)= \partial ( y, z)= i - 1$. A subset $Y$ of $X$ is said to be a completely regular code if the numbers p $_{ i, j}$= | G $_{ j}( x)$ Ç $Y | ( i, j$ Ĩ 0,1, frac14 , $d$) pi_i,j=|Gamma_j$(x)\cap Y|\quad $(i,j$\in \{0,1,\ldots,d\}$) depend only on $i= \partial ( x, Y)$ and $j$. A subset $Y$ of $X$ is said to be strongly closed if ${ x$ | P$( u, x) \sterling $ P$( u, v)$, P$( v, x)=1}$ Ì $Y$, whenever $u, v$ Ĩ $Y$. {x$\mid \partial(u,x)\leq \partial(u,v),\partial(v,x)=1\}\subset Y$,mbox whenever u,v$\in 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 $\Gamma $be a parallelogram-free distance-regular graph of diameter $d\geq 4$ such that every strongly closed subgraph of diameter two is completely regular. We show that $\Gamma $has 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 is $d - 2, \Gamma $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 is $d - 2$.

Détail

Keywords: keywords distance-regular graph, association scheme, homogeneity, completely regular code