Algorithmic aspects of algebraic methods for graph isomorphism testing

2006/02/04 by Michal Kaukič, Kaukic, Michal
Computer Science · Mathematics · #05C60 #05C85 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.math/0602071

openalex publication_date 2006/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present the implementation of an algorithm for graph isomorphism testing, based on ideas about number of walks (of sufficiently large length) between vertices. The algorithm is expanded for strongly regular graphs (SRG-s) by testing the local complements and values of determinants of their adjacency matrices. All known non-isomorphic SRG-s (with no more than 64 vertices) are distinguishable by this method.

Related

• Polynomial Time Algorithm for Graph Isomorphism Testing
• Fast Isomorphism Testing of Graphs with Regularly-Connected Components
• Isomorphism of graphs-a polynomial test
• The polynomial algorithm for graphs' isomorphism testing
• Discrimination of Graph Isomorphism Classes by Continuous Spectrum and Split Technique