Non-isomorphic graphs with cospectral symmetric powers (Q2380284)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5686823
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Non-isomorphic graphs with cospectral symmetric powers |
scientific article; zbMATH DE number 5686823 |
Statements
Non-isomorphic graphs with cospectral symmetric powers (English)
0 references
26 March 2010
0 references
Summary: 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.
0 references
0.90504515
0 references
0.8989477
0 references
0.88551676
0 references
0 references
0.8850439
0 references
0.8823002
0 references
0.88168347
0 references
0.8806642
0 references
