# zbMATH — the first resource for mathematics

A local approach to 1-homogeneous graphs. (English) Zbl 0964.05073
An equitable partition of a graph is a partition $$\{C_1,\dots ,C_s\}$$ of its vertices into cells, such that for all $$i$$ and $$j$$ the number $$c_{ij}$$ of neighbours, which a vertex in $$C_i$$ has in cell $$C_j$$, is independent of the choice of the vertex in $$C_i$$. For all vertices $$x$$ and $$y$$ of a graph $$\Gamma$$ we define $$D_j^h(x,y)= \Gamma_j(x)\cap \Gamma_h(y)$$. $$\Gamma$$ has the $$i$$-homogeneous property when the collection of non-empty sets $$D_j^h(x,y)$$ for any pair $$x,y$$ of vertices at distance $$i$$, is an equitable partition (Nomura). For vertices $$x$$ and $$y$$ of $$\Gamma$$ at distance $$i$$ let $$CAB_i(x,y)= \{C_i(x,y),A_i(x,y),B_i(x,y)\}$$. $$\Gamma$$ has the $$CAB_j$$ property, if for each $$i\leq j$$ the partition $$CAB_i(x,y)$$ is equitable for each pair of vertices $$x$$ and $$y$$ of $$\Gamma$$ at distance $$i$$. $$\Gamma$$ has the $$CAB$$ property, if $$\Gamma$$ has the $$CAB_d$$ property, where $$d$$ is a diameter of $$\Gamma$$. The local graphs of a distance-regular graph with $$a_1\neq 0$$ and $$CAB_1$$ property are either disjoint unions of $$(a_1+1)$$-cliques or connected strongly regular graphs with the same parameters (Proposition 2.1). Let $$\Gamma$$ be a distance-regular graph with $$a_1\neq 0$$. Then $$\Gamma$$ is 1-homogeneous if and only if it has the $$CAB$$ property (Theorem 3.1). In Section 4 a classification of the 1-homogeneous Terwilliger graphs with $$c_2\geq 2$$ is obtained.

##### MSC:
 5e+30 Association schemes, strongly regular graphs
Full Text: