Péter Madarasi: A new approach to graph isomorphism

In this talk, we present a graph isomorphism invariant that can be used to generate a well-managed "fingerprint" for graphs in an isomorphism invariant manner. We prove that fingerprints can distinguish more graph pairs than eigenalters with certain isomorphism invariant properties. We show that fingerprints uniquely identify "friendly" graphs, trees and 3-connected planar graphs. Finally, we prove that the fingerprints of k-connected graphs differ from those of non-k-connected graphs, where k is constant.