On symmetric association schemes and associated quotient-polynomial graphs

Fiol, Miquel A.¹ ; Penjić, Safet²

¹ Departament de Matemàtiques Universitat Politécnica de Catalunya Barcelona Graduate School of Mathematics Institut de Matemàtiques de la UPC-BarcelonaTech (IMTech) Catalonia, Spain
² University of Primorska Andrej Marušič Institute Muzejski trg 2 6000 Koper, Slovenia

Algebraic Combinatorics, Tome 4 (2021) no. 6, pp. 947-969

Résumé

Let $\Gamma$ denote an undirected, connected, regular graph with vertex set $X$, adjacency matrix $A$, and $d+1$ distinct eigenvalues. Let $𝒜=𝒜\left(\Gamma \right)$ denote the subalgebra of ${\mathrm{Mat}}_X\left(ℂ\right)$ generated by $A$. We refer to $𝒜$ as the adjacency algebra of $\Gamma$. In this paper we investigate algebraic and combinatorial structure of $\Gamma$ for which the adjacency algebra $𝒜$ is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) $𝒜$ has a standard basis $\{I,F_1,...,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,...,F_d\}$ then $F$ has $d+1$ distinct eigenvalues if and only if $\mathrm{span}\{I,F_1,...,F_d\}=\mathrm{span}\{I,F,...,F^d\}$. We describe the combinatorial structure of quotient-polynomial graphs with diameter $2$ and $4$ distinct eigenvalues. As a consequence of the techniques used in the paper, some simple algorithms allow us to decide whether $\Gamma$ is distance-regular or not and, more generally, which distance-$i$ matrices are polynomial in $A$, giving also these polynomials.

Détail

Reçu le : 2020-09-15
Révisé le : 2021-01-31
Accepté le : 2021-06-02
Publié le : 2022-01-04

DOI : 10.5802/alco.187

Classification : 05E30, 05C50
Keywords: Symmetric association scheme, adjacency algebra, quotient-polynomial graph, intersection diagram.

Licence : CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits