Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
By Afredo Alzaga, Rodrigo Iglesias, Ricardo Pignol. 2008
41 citations recorded by the source corpus.
The k-th power of an n-vertex graph X is the iterated cartesian product of X with itself. The k-th symmetric power of X is the quotient graph of certain subgraph of its k-th power by the natural action of the symmetric group. It is natural to ask if the spectrum of the k-th power - or the spectrum of the k-th symmetric power - is a complete graph invariant for small values of k, for example, for k=O(1) or k=O(logn). In this paper, we answer this question in the negative: we prove that if the well-known 2k-dimensional Weisfeiler-Lehman method fails to distinguish two given graphs, then their k-th powers - and their k-th symmetric powers - are cospectral. As it is well known, there are pairs of non-isomorphic n-vertex graphs which are not distinguished by the k-dim WL method, even for k=@W(n). In particular, this shows that for each k, there are pairs of non-isomorphic n-vertex graphs with cospectral k-th (symmetric) powers.
Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Electrical and Electronic Engineering
In Graph Learning
Citations in the corpus
- The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, methodology): “Note that these concepts of k-similarity and k-equivalence were used in [9] (and implicitly in [1]) to demonstrate that any two k-similar graphs have identical k-th symmetric powers, hence addressing the proposition of [3].”
- Non-Isomorphic Graphs with Cospectral Symmetric Powers (2009, background): “Indeed, from (6) it follows that X ⊂ Um where m = |U | and Um is defined as in (5) with X = U , d = m and R being the edge set of G′.”