19-25 June 2011

Bled, Slovenia

Europe/Ljubljana timezone

# On the Koolen - Park inequality and Terwilliger graphs

Presented by Alexander GAVRILYUK

Type: Oral presentation

Track: Association Schemes

## Content

A Terwilliger graph is a connected non-complete graph $\Gamma$ such that, for any two vertices $u,w\in \Gamma$ at distance $2$, the subgraph induced by the common neighbors of $u$ and $w$ is a complete graph of size $\mu$ (for some fixed $\mu \ge 1$). There are only three distance-regular Terwilliger graphs known with $\mu\ge 2$, all of them are characterized by theirs intersection arrays. The three examples are:
(1) the icosahedron with intersection array $\{5, 2, 1; 1, 2, 5\}$ is locally pentagon graph;
(2) the Doro graph with intersection array $\{10, 6, 4; 1, 2, 5\}$ is locally Petersen graph;
(3) the Conway–Smith graph with intersection array $\{10, 6, 4, 1; 1, 2, 6, 10\}$ is locally Petersen graph.
Let $\Gamma$ be a distance-regular graph with intersection array $\{b_0,b_1,...,b_{d-1};c_1,c_2,..,c_{d}\}$ and diameter $d\ge 2$. Let $c$ be maximal such that, for each vertex $x\in \Gamma$ and every pair of nonadjacent vertices $y,z$ of $\Gamma_1(x)$, there exists a $c$-coclique in $\Gamma_1(x)$ containing $y,z$. J.H. Koolen and J. Park showed that the following bound holds:
$$c_2-1\ge \frac{c(b_0-b_1)-b_0}{{c \choose 2}},$$
and equality implies that $\Gamma$ is a Terwilliger graph.
We prove that if the Koolen - Park bound is attained, then $c_2=2$ and $\Gamma$ is the icosahedron, the Doro graph or the Conway–Smith graph.

## Place

Location: Bled, Slovenia

Address: Best Western Hotel Kompas Bled