Non-Isomorphic Graphs with Cospectral Symmetric Powers
Open Access
- 7 January 2009
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 16 (1) , R120
Abstract
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.
Keywords
This publication has 8 references indexed in Scilit:
- Spectra of symmetric powers of graphs and the Weisfeiler–Lehman refinementsJournal of Combinatorial Theory, Series B, 2010
- Permutation group approach to association schemesEuropean Journal of Combinatorics, 2009
- Symmetric squares of graphsJournal of Combinatorial Theory, Series B, 2007
- Forestal algebras and algebraic forests (on a new class of weakly compact graphs)Discrete Mathematics, 2000
- Separability Number and Schurity Number of Coherent ConfigurationsThe Electronic Journal of Combinatorics, 2000
- On Highly Closed Cellular Algebras and Highly Closed IsomorphismsThe Electronic Journal of Combinatorics, 1998
- Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power qJournal of Combinatorial Theory, Series B, 1994
- An optimal lower bound on the number of variables for graph identificationCombinatorica, 1992