




















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。