Counting Walks - a Novel Approach to the Graph Isomorphism Problem
Date: 2017
Subject: mathematics
Matematikus TDK
TDK dolgozat
Matematikus TDK
TDK dolgozat
Abstract:
This paper presents the concept of walk-labeling that can be used to decide
the graph isomorphism problem in polynomial time combinatorially under
certain conditions - which hold for a wide range of the graph pairs. It turns
out that all non-cospectral graph pairs can be differentiated with a combinatorial
method, furthermore, even if the graphs are cospectral and nonisomorphic,
they might be distinguished by combinatorially verifying certain
properties of their eigenspaces.
Strong walk-labeling, a strengthening of the aforementioned labeling, has
also been introduced for practical purposes. Its applications include speeding
up any backtracking graph matching algorithm, and the generation of graph
fingerprints, which identify all the graphs uniquely it was tested on, including
all known strongly regular graphs.
To practically evaluate the new methods, tests have been carried out on
biological, strongly regular and random graph.