OFFSET
0,4
COMMENTS
The symmetry type of an undirected graph is determined by its automorphism group. It is a permutation group on the nodes set. Since every undirected graph may be understood as a directed graph with symmetric edges, the automorphism group of a graph with n nodes is always an automorphism group of a digraph with the same nodes size. Therefore A343592 is an upper bound for this sequence.
LINKS
Peter Dolland, Graph Symmetry Tables for n = 3..8
Götz Pfeiffer, Subgroups. [broken link]
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.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Peter Dolland, Jul 28 2021
EXTENSIONS
a(9)-a(10), found using GAP, from James Mitchell, Nov 17 2023
STATUS
approved