Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements

DOI10.1016/j.jctb.2010.07.001zbMath1208.05086arXiv0801.2322OpenAlexW2024187520MaRDI QIDQ602723

Rodrigo Iglesias, Afredo Alzaga, Ricardo Pignol

Publication date: 5 November 2010

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0801.2322

zbMATH Keywords

random walksgraph spectragraph isomorphism problemWeisfeiler-Lehman algorithm

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random walks on graphs (05C81)

Related Items (15)

On the Combinatorial Power of the Weisfeiler-Lehman Algorithm ⋮ Droplet states in quantum XXZ spin systems on general graphs ⋮ Edge-transitive token graphs ⋮ The connectivity of token graphs ⋮ On the Connectivity of Token Graphs of Trees ⋮ Automorphism group of 2-token graph of the Hamming graph ⋮ The automorphism groups of some token graphs ⋮ Spectral properties of token graphs ⋮ The automorphisms of 2-token graphs ⋮ Independence and matching numbers of some token graphs ⋮ Descriptive complexity of graph spectra ⋮ Hamiltonicity of token graphs of fan graphs ⋮ On the Laplacian spectra of token graphs ⋮ The edge-connectivity of token graphs ⋮ Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations

Cites Work

• Unnamed Item
• Unnamed Item
• Symmetric squares of graphs
• An optimal lower bound on the number of variables for graph identification
• Equivalence in finite-variable logics is complete for polynomial time
• Isomorphism testing for embeddable graphs through definability
• Random Graph Isomorphism

This page was built for publication: Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements