Page 330 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 330
SPECTRAL GRAPH THEORY (MS-46)
On symmetric association schemes and associated quotient-polynomial
graphs
Safet Penjic´, safet.penjic@iam.upr.si
University of Primorska, Slovenia
Coauthor: Miquel Àngel Fiol Mora
Let Γ denote an undirected, connected, regular graph with vertex set X, adjacency matrix
A, and d + 1 distinct eigenvalues. Let A = A(Γ) denote the subalgebra of MatX(C) gen-
erated by A. We refer to A as the adjacency algebra of Γ. In this talk we investigate al-
gebraic and combinatorial structure of Γ for which the adjacency algebra A is closed under
Hadamard multiplication. In particular, under this simple assumption, we show the following:
(i) A has a standard basis {I, F1, . . . , Fd}; (ii) for every vertex there exists identical distance-
faithful intersection diagram of Γ with d + 1 cells; (iii) the graph Γ is quotient-polynomial;
and (iv) if we pick F ∈ {I, F1, . . . , Fd} then F has d + 1 distinct eigenvalues if and only
if span{I, F1, . . . , Fd} = 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
technique from the paper we give an algorithm which computes the number of distinct eigen-
values of any Hermitian matrix using only elementary operations. When such a matrix is the
adjacency matrix of a graph Γ, a simple variation of the algorithm allow us to decide whether Γ
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.
328
On symmetric association schemes and associated quotient-polynomial
graphs
Safet Penjic´, safet.penjic@iam.upr.si
University of Primorska, Slovenia
Coauthor: Miquel Àngel Fiol Mora
Let Γ denote an undirected, connected, regular graph with vertex set X, adjacency matrix
A, and d + 1 distinct eigenvalues. Let A = A(Γ) denote the subalgebra of MatX(C) gen-
erated by A. We refer to A as the adjacency algebra of Γ. In this talk we investigate al-
gebraic and combinatorial structure of Γ for which the adjacency algebra A is closed under
Hadamard multiplication. In particular, under this simple assumption, we show the following:
(i) A has a standard basis {I, F1, . . . , Fd}; (ii) for every vertex there exists identical distance-
faithful intersection diagram of Γ with d + 1 cells; (iii) the graph Γ is quotient-polynomial;
and (iv) if we pick F ∈ {I, F1, . . . , Fd} then F has d + 1 distinct eigenvalues if and only
if span{I, F1, . . . , Fd} = 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
technique from the paper we give an algorithm which computes the number of distinct eigen-
values of any Hermitian matrix using only elementary operations. When such a matrix is the
adjacency matrix of a graph Γ, a simple variation of the algorithm allow us to decide whether Γ
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.
328
