## 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 n0,15 degrees are distinct. In fact, they are pairwise at least n0,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