Polynomial Time Symmetry and Isomorphism Testing for Connected Graphs

2006/12/01 by Matthew Delacorte, Delacorte, Matthew
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Theory and Algorithms #Graph theory and applications #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0612001

arxiv created 2006/12/01 · openalex publication_date 2006/12/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We use the concept of a Kirchhoff resistor network (alternatively random walk on a network) to probe connected graphs and produce symmetry revealing canonical labelings of the graph(s) nodes and edges.

Citations

• A measure of betweenness centrality based on random walks

Related

• Polynomial Time Algorithm for Graph Isomorphism Testing
• New Invariants for the Graph Isomorphism Problem
• Approximate Network Symmetry
• Isotropic covariance functions on graphs and their edges
• Generating Graphs with Symmetry