A local approach to 1-homogeneous graphs. (English) Zbl 0964.05073

Jurišić, Aleksandar; Koolen, Jack

Des. Codes Cryptography 21, No. 1-3, 127-147 (2000).

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.

Reviewer: Alexandre A.Makhnev (Ekaterinburg)

MSC:

05E30

Association schemes, strongly regular graphs

Keywords:

distance-regular graphs; locally strongly regular; partition