|
|
EXAMPLE
|
The 6 symmetry types of the 11 graphs with n = 4 nodes are represented by:
1.) {}, the empty graph has together with the full graph the automorphism group S_4 (as subgroup of S_4) as symmetry type.
2.) {(1,2)} has together with its complement the group <(1,2),(3,4)> with structure C_2^2 as automorphisms.
3.) {(1,2),(1,3)} has together with its complement the group <(2,3)> with structure C_2 as automorphisms.
4.) {(1,2),(3,4)} has together with its complement the group <(1,2),(1,3)(2,4)> with structure C_2^3 as automorphisms.
5.) {(1,2),(1,3),(1,4)} has together with its complement the symmetric group S_3 on the elements {2,3,4} as automorphisms.
6.) {(1,2),(1,3),(2,4)} is self-complementary with automorphism group <(1,2)(3,4)> having the structure C_2 too.
The total of the sizes of the symmetry type classes yields the number of graphs A000088. Here: 5*2+1 = 11 = A000088(4).
The indices of the automorphism groups are 1,6,12,3,4,12. There are 2*(1+6+12+3+4)+12 = 64 = 2^(4*3/2) = A006125(4) possibilities, to label the nodes with 1,...,4 of all the graphs.
The cycle types of the automorphism groups enable to compute the possibilities to mark a subset of the nodes. With the results 5,9,12,6,8,10 we get 2*(5+9+12+6+8)+10 = 90 = A000666(4), what can be interpreted as the number of undirected graphs with loop edges.
|
