Descriptive complexity of graph spectra
Descriptive complexity of graph spectra
复制标题
图谱的描述复杂性
DOI：
10.1016/j.apal.2019.04.005
复制
发表时间：
2019
影响因子：
0.8
通讯作者：
Dawar A
中科院分区：
文献类型：
--
作者：
Dawar A
如果两个图各自的邻接矩阵具有相同的多特征值集，则它们是共谱图。如果与一个图同谱的图都是同构的，那么这个图就是由它的谱决定的。我们考虑这些属性与逻辑可定义性的关系。我们证明了关于三变量计数一阶逻辑c3的任何一对图的初等等价都是共谱的，而对于c2则不是这样，如果我们排除计数量词，对于任何数量的变量也不是这样。我们还证明了一类由谱决定的图在有计数的部分不动点逻辑中是可定义的。我们把这些性质与其他代数和组合问题联系起来。
Two graphs are cospectral if their respective adjacency matrices have the same multi-set of eigenvalues. A graph is said to be determined by its spectrum if all graphs that are cospectral with it are isomorphic to it. We consider these properties in relation to logical definability. We show that any pair of graphs that are elementarily equivalent with respect to the three-variable counting first-order logic C 3 are cospectral, and this is not the case with C 2, nor with any number of variables if we exclude counting quantifiers. We also show that the class of graphs that are determined by their spectra is definable in partial fixed-point logic with counting. We relate these properties to other algebraic and combinatorial problems.