Name
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. |
Year | Venue | Field |
|---|---|---|
2009 | ELECTRONIC JOURNAL OF COMBINATORICS | Discrete mathematics,Combinatorics,Vertex-transitive graph,Graph isomorphism,Graph homomorphism,Chordal graph,Foster graph,Independent set,Symmetric graph,Mathematics,Complement graph |
DocType | Volume | Issue |
Journal | 16.0 | 1.0 |
ISSN | Citations | PageRank |
1077-8926 | 8 | 0.68 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amir Rahnamai Barghi | 1 | 9 | 2.79 |
| Ilya Ponomarenko | 2 | 10 | 1.67 |