|
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:
| AUTHOR | = | {Jüttner, Alp{\'a}r and Madarasi, P{\'e}ter}, |
| TITLE | = | {A novel approach to graph isomorphism}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2019}, |
| NUMBER | = | {TR-2019-17} |