Random Graph Isomorphism 论文

摘要

A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs (i.e. all but $o(2^{( \begin{subarray}{l} n \\ 2 \end{subarray} )} )$) of the $2^{( \begin{subarray}{l} n \\ 2 \end{subarray} )} $ 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.