e equitable refinements of the initial partition given by the coloring. Elements of the search tree are called nodes so as not to confuse them with the vertices of the graph. The root of the search tree is the equitable refinement of the initial coloring. Branches are formed by individualizing vertices and finding successive equitable refinements after each indi vidualization step. Each movement down the search tree corresponds to individualizing an appropriate vertex and finding the equitable refinement of the resulting parti tion. Thus, each node at distance k from the root of the search tree can be represented by an ordered k tuple of vertices, with the ordering corresponding to the order of vertex individualization. The leaves of the search tree correspond to discrete parti tions.

Thus, each terminal node has a natural associa tion with a permutation of the vertices of the graph. The key idea is that automorphisms of the graph cor respond to similar leaves in the search tree. To be more precise, we say that two permutations, ��1 and ��2, of the vertices of the graph are equivalent if there is an auto morphism of the graph, g such that ��1 ��2 g Then as g is a permutation of the vertices, it can also be considered a permutation of the nodes of the search tree. It can be shown that if �� is a node of the search tree, then ��g will be as well. In fact, much more is true, the two sets of leaves of the search tree derived from the two nodes �� and ��g, respec tively, will be equivalent to each other. In other words, ming from a given node �� in the search tree, and we can ignore the terminal nodes stemming from ��g.

In this way, knowledge of automorphisms can be used to eliminate the AV-951 need to examine parts of the search tree. Nauty discovers automorphisms in the following way. The algorithm is based on depth first search, it immedi ately starts generating terminal nodes. Upon producing a terminal node, Nauty applies the corresponding per mutation to the original graph and then calculates the resulting adjacency matrix. Two adjacency matrices pro duced in this way are equal if and only if the corre sponding two permutations, ��1 and ��2, are equivalent. In this case, there exists an automorphism g of the graph such that ��1 ��2 g. The Nauty algorithm then calculates g by evaluating ? 21 ?1. As such automorph isms are discovered, Nauty can prune the size of the search tree as detailed above.

Nauty also uses an indicator function to further prune the search tree. An indicator function is a map defined on the nodes of the search tree that is invariant under automorphisms of the graph. This function maps the nodes into a linearly ordered set Then Nauty skips over nodes of the search tree where the indicator function is not minimal. As the indicator function is invariant under automorphisms of the graph, a canonical label will be found among those terminal nodes of minimal indicator function value. HNauty Here we describe HNauty and explain how HNauty dif fers from Mc