Non-Isomorphic Graphs with Cospectral Symmetric Powers
Non-Isomorphic Graphs with Cospectral Symmetric Powers
复制标题
具有共谱对称幂的非同构图
DOI：
10.37236/209
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
I. Ponomarenko
中科院分区：
文献类型：
--
作者：
A. Barghi;I. Ponomarenko
图的对称 $m$ 次幂是这样的图，其顶点是顶点的 $m$ 子集，并且其中两个 $m$ 子集相邻当且仅当它们的对称差是原始图的一条边。据推测，存在一个固定的 $m$，使得任意两个图同构当且仅当它们的 $m$ 对称幂是共谱的。在本文中，我们证明，给定一个正整数 $m$，存在无限多对具有共谱 $m$ 对称幂的非同构图。我们的构建基于相干构型的多维扩展理论。
The symmetric $m$-th power of a graph is the graph whose vertices are $m$-subsets of vertices and in which two $m$-subsets are adjacent if and only if their symmetric difference is an edge of the original graph. It was conjectured that there exists a fixed $m$ such that any two graphs are isomorphic if and only if their $m$-th symmetric powers are cospectral. In this paper we show that given a positive integer $m$ there exist infinitely many pairs of non-isomorphic graphs with cospectral $m$-th symmetric powers. Our construction is based on theory of multidimensional extensions of coherent configurations.