The authors deal with finding graph automorphisms in terms of finding the equivalence classes induced by the automorphisms. The squeeze tree search is a search tree for permutation of vertices--the permuted position of each vertex defining the nodes of the tree. If the classes are labeled by the vertices, a permutation can be discarded as soon as Perm (i) is seen to be non-equivalent to i.

The test of equivalence is carried out by testing equivalences under some other partition known to be coarser than the automorphism. The authors have suggested a good number of them. A well-known one is: two vertices are equivalent if their degrees are equal. A refinement of this is to map each vertex into a sequence of equivalence classes--its own and the ones of the vertices connected to it. The equivalence generated by this map refines the original equivalence, but is still coarser than the automorphism equivalence. This is called the “neighbor- hood class.” Repeated applications of this refinement yields the “adjacency partition” for the neighborhood class equivalence.

One can also refine the degree equivalence by a vector whose components are the count of the number of vertices at distance 1 (the “degree”), the numbers at distance 2, 3,. . ., etc. This yields the “distance signature,” and the adjacency partition included by it is the “distance signature partition.”

Finer equivalences (still preserving automorphism) can be obtained by transforming the graph into a new one before taking their degree equivalence or one of its refinements. One such transformation is to add a new vertex on each arc. The distance signature partitions of these transforms mapped back to the original graph yields a partition as fine as the automorphism partition for many strongly regular graphs.

Other graph transforms that yield good results are obtained by placing more than one vertex on each arc. One can also use a transform where the vertices are edges and two edges are adjacent if they are incident on the same vertex. This transformation can also be applied repeatedly to obtain other automorphism-preserving partitions. The paper is exemplary in its clarity and precision.