Certificates for undirected graphs

grantor: University of TorontoAn isomorphism certificate (I.C.) for a graph is a set of labeled edges which in combination with an isomorphic copy of a graph allows its errorless reconstruction. Work by Rubinstein, an economist, on binary relations first motivated work on the minimum size of I.C.s for tournaments. This thesis marks the first work on I.C.s for undirected graphs. It provides a structure upon which all further work on I.C.s can be based. As well it introduces the concept of using edges which are in the complement of the graph (non-edges) to provide extra information. The bulk of the work done is on valid and optimal I.C.s for several graphs. We look at wheels, complete binary trees, complete k-ary trees, and grids. For the grid we were unable to prove our I.C. is optimal but an asymptotically correct upper bound was found on the size of the minimum I.C.M.Sc