Contents
- Index

**NETWORKS>ROLES&POSITIONS>AUTOMORPHIC>ALL PERMUTATIONS**

**PURPOSE** Partitions the vertices of a graph into orbits by exhaustive search.

**DESCRIPTION **Two vertices u and v of a labeled graph G are automorphically equivalent if all the vertices can be relabeled to form an isomorphic graph with the labels of u and v interchanged. Automorphic equivalence is an equivalence relation and therefore partitions the vertices into equivalence classes called orbits. This routine finds the orbits by examining all possible relabellings of the graph. For a graph of n vertices there are n! possible Permutations of the labels.

**PARAMETERS**

* ***Input dataset:**

Name of file containing network to be analyzed. Data type: Digraph.

* *

* ***(Output) Orbit Dataset*** *(Default = 'AllAutomorphismsOrbits').

Name of output file to contain orbit indicator vector. This vector has the form (k1,k2,...ki...) where ki assigns vertex i to orbit ki, so that (1 1 2 1 2) assigns vertices 1, 2 and 4 to orbit 1 and 3 and 5 to orbit 2. This vector is not displayed in the LOG FILE.

**(Output Automorphism Dataset):** (Default = AllAutomorphismsAuto').

Name of file which that gives all automorphisms of the graph. The automorphisms are specified in a numbered list with the original labeling at the head. A value of k in row m column n means that for automorphism number m vertex n was relabeled k.This vector is not displayed in the LOG FILE.

**LOG FILE** The number of Permutations examined.

The number of relabellings that produced an isomorphism.

The percentage of all permutations that produced an isomorphic graph (the hit rate).

A list of the orbits.

**TIMING** Exponential.

**COMMENTS** Computation time for this routine is very slow. It is inadvisable to try this on graphs with more than 10 vertices, impossible on graphs with more than 15.

**REFERENCES
**