login
A346673
Number of symmetry types of undirected graphs with n unlabeled nodes.
1
1, 1, 1, 2, 6, 9, 23, 31, 71, 103, 213
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
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
Cf. A343592, the analog for directed graphs.
Cf. A000088, total number of undirected graphs with unlabeled nodes.
Cf. A006125, total number of undirected graphs with labeled nodes.
Cf. A000666, total number of undirected graphs with reflexive edges.
Sequence in context: A318193 A048083 A127931 * A077237 A056879 A006746
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