New Invariants for the Graph Isomorphism Problem

Resumo

Abstract

In this paper, we introduce a novel polynomial-time algorithm to compute graph invariants based on the idea of a modified random walk on graphs. Though not proved to be a full graph invariant yet, our method gives the right answer for the graph instances other well-known methods could not compute (such as special Fürer gadgets and point-line incidence graphs of finite projective planes of higher degrees).