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.