论文标题
图形的广义光谱的描述性复杂性
Descriptive complexity of the generalized spectra of graphs
论文作者
论文摘要
如果它们各自的邻接矩阵具有相同的特征值的多种矩阵，并且合而为一，则两个图是共同的，如果它们是共同的，则它们的补充也是如此。我们研究了与逻辑确定性有关的广泛合作感。我们表明，相对于三变量计数的一阶逻辑$ c^3 $的任何基本图表都是广义的，而不是$ c^2 $的情况，也不是任何数量的变量，如果我们排除计数量词。使用此结果，我们使用逻辑$ c^3 $提供了众所周知的距离定型图的新表征。我们还表明，对于可控制的图（众所周知，几乎所有图形都是可控的），$ c^2 $中的基本等价与同构相吻合。
Two graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues, and generalized cospectral if they are cospectral and so are their complements. We study generalized cospectrality in relation to logical definability. We show that any pair of graphs that are elementary equivalent with respect to the three-variable counting first-order logic $C^3$ are generalized cospectral, and this is not the case with $C^2$, nor with any number of variables if we exclude counting quantifiers. Using this result we provide a new characterization of the well-known class of distance-regular graphs using the logic $C^3$. We also show that, for controllable graphs (it is known that almost all graphs are controllable), the elementary equivalence in $C^2$ coincides with isomorphism.
