邻接代数

在代数图论中，图$G$的邻接代数（adjacency algebra）是这个图的邻接矩阵$A(G)$的多项式所组成的代数。它是一种矩阵代数，是$A$的各次幂的线性组合所组成的集合。

其他一些类似的数学对象也被称为“邻接代数”。

性质

$G$的邻接代数的性质与$G$的图论性质相关，例如各种谱、邻接性、连通性。

命题：顶点$i,j$之间长度为$d$路径的数目等于$A^{d}$的$(i,j)$元。

命题：对于直径为$d$的连通图，其邻接代数的维数至少是$d+1$。

推论：直径为$d$的连通图至少有$d+1$个不同的特征值。

参考文献

• Algebraic graph theory, by Norman L. Biggs, 1993, ISBN 0521458978, p. 9