##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 454.05038

**Autor: ** Babai, Laszlo; Erdös, Paul; Selkow, Stanley M.

**Title: ** Random graph isomorphism. (In English)

**Source: ** SIAM J. Comput. 9, 628-635 (1980).

**Review: ** A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs (i.e. all but O(2^{\binom n2}) of the 2^{\binom n2}) graphs on n vertices). Hence, for almost all graphs X, and graph Y can be easily tested for isomorphism to X by an extremly 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.

**Classif.: ** * 05C35 Extremal problems (graph theory)

68Q20 Nonnumerical algorithms

**Keywords: ** isomorphism testing; canonical labeling; random graph; linear time; degree sequence of a graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag