cp's OEIS Frontend

A346673 Number of symmetry types of undirected graphs with n unlabeled nodes.

%I A346673 #36 Nov 19 2023 11:35:49
%S A346673 1,1,1,2,6,9,23,31,71,103,213
%N A346673 Number of symmetry types of undirected graphs with n unlabeled nodes.
%C A346673 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.
%H A346673 Peter Dolland, <a href="/A346673/a346673.pdf">Graph Symmetry Tables for n = 3..8</a>
%H A346673 Götz Pfeiffer, <a href="http://schmidt.nuigalway.ie/subgroups">Subgroups</a>. [broken link]
%e A346673 The 6 symmetry types of the 11 graphs with n = 4 nodes are represented by:
%e A346673 1.) {}, the empty graph has together with the full graph the automorphism group S_4 (as subgroup of S_4) as symmetry type.
%e A346673 2.) {(1,2)} has together with its complement the group <(1,2),(3,4)> with structure C_2^2 as automorphisms.
%e A346673 3.) {(1,2),(1,3)} has together with its complement the group <(2,3)> with structure C_2 as automorphisms.
%e A346673 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.
%e A346673 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.
%e A346673 6.) {(1,2),(1,3),(2,4)} is self-complementary with automorphism group <(1,2)(3,4)> having the structure C_2 too.
%e A346673 The total of the sizes of the symmetry type classes yields the number of graphs A000088. Here: 5*2+1 = 11 = A000088(4).
%e A346673 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.
%e A346673 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.
%Y A346673 Cf. A343592, the analog for directed graphs.
%Y A346673 Cf. A000088, total number of undirected graphs with unlabeled nodes.
%Y A346673 Cf. A006125, total number of undirected graphs with labeled nodes.
%Y A346673 Cf. A000666, total number of undirected graphs with reflexive edges.
%K A346673 nonn,more
%O A346673 0,4
%A A346673 _Peter Dolland_, Jul 28 2021
%E A346673 a(9)-a(10), found using GAP, from _James Mitchell_, Nov 17 2023