Random Graph Isomorphism

A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs, and any graph Y can be easily tested for isomorphism to X by an extremely naive linear time algorithm.

Abstract

A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs (i.e. all but o(2 (2>) of the 2 t 1 graphs on n vertices). Hence, for almost all graphs X, any graph Y can be easily tested for isomorphism to X by an extremely naive linear time algorithm. This result is based on the following: In almost all graphs on n vertices, the largest n^0.15 degrees are distinct. In fact, they are pairwise at least n^0.03 apart.