Isomorphism certificates for undirected graphs

摘要

For a graph G, we are interested in a minimum-size subgraph of G which, along with an unlabeled copy of G, provides enough information to reconstruct G. We perform a preliminary study of such subgraphs, focusing on the cases where G is a complete tree or a grid.