19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

On the Koolen - Park inequality and Terwilliger graphs

Presented by Alexander GAVRILYUK
Type: Oral presentation
Track: Association Schemes


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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors