TR-2019-17

A novel approach to graph isomorphism

Alpár Jüttner, Péter Madarasi



Abstract

This paper presents the concept of \emph{walk-labeling} that can be used to design polynomial algorithm for solving the graph isomorphism problem for various graph classes. For example, all non-cospectral graph pairs can be distinguished by the proposed combinatorial method. Furthermore, even non-isomorphic co-spectral graphs might be distinguished assuming certain properties of their eigenspaces.
 
The concept of \emph{$k$-strong walk-labeling} is a refinement of the aforementioned labeling, which has both theoretical and practical applications. Its applications include the generation of graph fingerprints, which uniquely identify all the graphs in the considered databases -- including all strongly regular graphs on at most 64 nodes and all graphs on at most 12 nodes. They provably identify all trees and 3-connected planar graphs up to isomorphism, which -- as a byproduct -- gives a new isomorphism algorithm for both graph classes. The practical importance of this fingerprint lies in significantly speeding up searching in graph databases and graph matching algorithms, which are commonly required in biological and chemical applications.


Bibtex entry:

@techreport{egres-19-17,
AUTHOR = {Jüttner, Alp{\'a}r and Madarasi, P{\'e}ter},
TITLE = {A novel approach to graph isomorphism},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-17}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!