On symmetric association schemes and associated quotient-polynomial graphs

Abstract

Let $\Gamma$ denote an undirected, connected, regular graph with vertex set $X$, adjacency matrix $A$, and $d+1$ distinct eigenvalues. Let $\mathcal{A}=\mathcal{A}(\Gamma )$ denote the subalgebra of Mat${}_X(\mathbb{C})$ generated by $A$. We refer to $\mathcal{A}$ as the {\it adjacency algebra} of $\Gamma$. In this paper we investigate algebraic and combinatorial structure of $\Gamma$ for which the adjacency algebra $\mathcal{A}$ is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) $\mathcal{A}$ has a standard basis $\{I,F_1,\dots ,F_d\}$; (ii) for every vertex there exists identical distance-faithful intersection diagram of $\Gamma$ with $d+1$ cells; (iii) the graph $\Gamma$ is quotient-polynomial; and (iv) if we pick $F\in \{I,F_1,\dots ,F_d\}$ then $F$ has $d+1$ distinct eigenvalues if and only if span$\{I,F_1,\dots ,F_d\}=$span$\{I,F,\dots ,F^d\}$. We describe the combinatorial structure of quotient-polynomial graphs with diameter $2$ and $4$ distinct eigenvalues. As a consequence of the technique from the paper we give an algorithm which computes the number of distinct eigenvalues of any Hermitian matrix using only elementary operations. When such a matrix is the adjacency matrix of a graph $\Gamma$, a simple variation of the algorithm allow us to decide wheter $\Gamma$ is distance-regular or not. In this context, we also propose an algorithm to find which distance-$i$ matrices are polynomial in $A$, giving also these polynomials.

22 pages plus 4 pages of references