Isomorphism Testing and Symmetry of Graphs

DOI10.1016/S0167-5060(08)70857-4MaRDI QIDQ3884133zbMATH OpenOpenAlexFDO

Authors László Babai

Publication date 1980

Published in Combinatorics 79 Part I (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-5060(08)70857-4

zbMATH Keywords

automorphism groupcomplexity of graph isomorphism testingcubic graphsgraphs with bounded eigenvalue multiplicitiesgraphs with colored vertices with small color- classesgraphs with primitive automorphism groupsMonte-Carlo algorithmsrandom graphsreducibilitystrongly regular graphs

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Software, source code, etc. for problems pertaining to combinatorics (05-04) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cited in

(7)

• Graph isomorphism problem
• Le problème d'étoiles pour graphes est NP-complèt
• On bipartite distance-regular Cayley graphs with small diameter
• On the complexity of reconstructing H-free graphs from their Star Systems
• On the Complexity of Reconstructing H-free Graphs from Their Star Systems
• Switching for small strongly regular graphs
• A new measure of symmetry and its application to classification of bifurcating structures

This page was built for publication: Isomorphism Testing and Symmetry of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3884133)