论文标题
关于对称关联方案和相关的商 - 多项式图
On symmetric association schemes and associated quotient-polynomial graphs
论文作者
论文摘要
令$γ$表示带有顶点$ x $，邻接矩阵$ a $和$ {d+1} $不同的特定eigenvalues的无向，连接的常规图。令$ {\ mathcal a} = {\ Mathcal a}（γ）$表示由$ a $生成的Mat $ _X（{\ Mathbb C}）$的sibalgebra。我们将$ {\ Mathcal a} $称为$γ$的{\ it邻接代数}。在本文中，我们调查了$γ$的代数和组合结构，在Hadamard乘法下关闭了相邻代数$ {\ Mathcal a} $的代数和组合结构。特别是，在这个简单的假设下，我们显示以下内容：（i）$ {\ mathcal a} $具有标准基础$ \ {i，f_1，\ ldots，f_d \} $; （ii）对于每个顶点，存在$γ$的相同距离信仰的交叉图与$ d+1 $ $ $ clible； （iii）图$γ$是商 - 多项式； （iv）如果我们选择$ f \ in \ {i，f_1，\ ldots，f_d \} $，则$ f $具有$ d+1 $ dintife eigenvalues，并且仅当且仅当span $ \ {i，f_1，\ ldots，f_1，\ ldots，f_d \}，f_d \} = $ span = $ spas $ \ \ \ c $ \ {i，f，f，f，f，f，f，f，f，f，ld.我们描述了直径$ 2 $和$ 4 $不同的特征值的商 - 多项式图的组合结构。由于本文的技术，我们提供了一种算法，该算法仅使用基本操作来计算任何遗产矩阵的不同特征值的数量。当这样的矩阵是图$γ$的邻接矩阵时，算法的简单变化使我们可以决定是否距离$γ$是距离的。在这种情况下，我们还提出了一种算法，以查找哪种距离为$ a $ a $ $ a $的距离，也提供了这些多项式。
Let $Γ$ denote an undirected, connected, regular graph with vertex set $X$, adjacency matrix $A$, and ${d+1}$ distinct eigenvalues. Let ${\mathcal A}={\mathcal A}(Γ)$ denote the subalgebra of Mat$_X({\mathbb C})$ generated by $A$. We refer to ${\mathcal A}$ as the {\it adjacency algebra} of $Γ$. In this paper we investigate algebraic and combinatorial structure of $Γ$ 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,\ldots,F_d\}$; (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\in \{I,F_1,\ldots,F_d\}$ then $F$ has $d+1$ distinct eigenvalues if and only if span$\{I,F_1,\ldots,F_d\}=$span$\{I,F,\ldots,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 $Γ$, a simple variation of the algorithm allow us to decide wheter $Γ$ 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.
