Non-Isomorphic Graphs with Cospectral Symmetric Powers
By Amir Rahnamai Barghi, Ilia N. Ponomarenko. 2009
38 citations recorded by the source corpus.
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.
Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering, Geometry and Topology, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Discrete Mathematics and Combinatorics
In Electrical and Electronic Engineering
In Geometry and Topology
In Algorithms & Complexity
Citations in the corpus
- The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, methodology): “[3] proposed a graph isomorphism method based on the symmetric powers of the adjacency matrix of a graph, which was later shown in [1] and [9] to be no more effective than the k-dim WL method.”