How to Read the ‚Digraph Symmetry Tables‘
A Digraph Symmetry Table lists digraphs of the different symmetries to a given count of n nodes. The symmetry type of a digraph is determined by its automorphism group. It is a permutation group on the nodes set, and therefore a subgroup of the symmetric group Sn. The total number of these is determined by https://oeis.org/A000638 . But not all of them occur as automorphism group of a digraph.
The Digraph Symmetry Tables presented here bases on an enumeration algorithm sorting out digraphs with a symmetry already found. Therefore the shown digraph is the first one found by the algorithm. Since it lists the digraphs with increasing edge count, its minimality is guaranteed for each symmetry type.
Example:
Edge count with the relative position.
ID: The position of this digraph
in the creation sequence. Number of possibilities to mark a subset of the nodes.
Number of possibilities to label the nodes with 1..n. The number of digraphs with this symmetry.
Cycle type of this automorphism
group without leading 1. Here: 1
double transposition and 2 4-cycle moves. The name of the automorphism group in
http://schmidt.nuigalway.ie/subgroups .
The cumulative cycle type of the permutation group indicates the quantity of member permutations, whose cycle type yields a specific partition of n. The partitions are listed in graded lexicographical ordering (see https://oeis.org/A193073 ) omitting the first one (1n) representing the identity. For n = 6 there are 10 non-trivial partitions with (2,14), (22,12), (23), (3,13), (3,2,1), (32), (4,12), (4,2), (5,1), (6), see also https://oeis.org/A000041 .
The cycle type may be used to calculate different quantities. Especially the order of the permutation group is just the sum s of its values. n!/s yields the index of the group in Sn and therefore the number of possibilities to label the nodes with the numbers 1..n, here designated with _TO. Multiplied with the number of digraphs with this symmetry we have the contribution of this symmetry type to the number of the labeled digraphs, which is in total 2^(n2-n), see also https://oeis.org/A053763 .
It is implicitely clear, that the sum over all digraph quantities of a symmetry table results in the total of digraphs with n nodes represented by https://oeis.org/A000273 . The automorphism group of asymmetric digraphs is trivial containing the identity id as the only member. Therefore those digraph quantity accords https://oeis.org/A051504 .
The calculation of the number of possibilities to mark a subset of nodes, here designated with _R, bases on the Pólya enumeration theorem. Each permutation ? is assigned to the number z(?) of cycles in ?, whereby fixpoints are cycles for its own. If ? has the cycle type (22,12), so z(?)=4. With Pólya we get
for a digraph G with automorphism group Aut(G). Using the cumulative cycle type of Aut(G) with order s and the assignment q to the partitions of n, we may formulate alternatively:
If we understand the marking of a subset of the nodes as a reflexive addition to the digraph yielding an arbitrary binary relation, we see, that the total of the _R values multiplied with the digraph quantities results in the values of https://oeis.org/A000595 .
http://schmidt.nuigalway.ie/subgroups/alt.html lists all the subgroups of Sn for n=5,…,12. The identifications referring [ATLAS] are taken from there with the exception that Cn is used instead of simply „n“ for the cyclic group with n elements. Note, that different permutation groups may have the same group structure, i.e. may be isomorph. E.g. S6 contains 3 different subgroups of the isomorphism class C2: C2a, C2b, and C2c, all with different cycle types. But however, different permutation groups may also have the same cycle type: In S6 the subgroups C22a and C22b have the same cycle type [0,3,0,…], but they both do not occur as automorphism groups of a digraph with six nodes. And in S6 all other subgroups have different cycle types. So we can say, that the cycle type identifies the automorphism group for n ? 6. But there is no such statement for n > 6.
By the way: The number of the different orders of the subgroups of Sn is given by https://oeis.org/A218913 . The number of the different group isomorphism classes of the subgroups of Sn is given by https://oeis.org/A174511 .
References
[ATLAS]
John H. Conway, Robert T. Curtis, Simon P. Norton, Richard A. Parker, and Robert A. Wilson, Atlas of ?nite groups, Oxford
University Press, 1985.