cp's OEIS Frontend

A343592 Number of symmetry types of digraphs with n nodes.

%I A343592 #23 Apr 20 2023 10:03:58
%S A343592 1,2,4,9,14,36
%N A343592 Number of symmetry types of digraphs with n nodes.
%C A343592 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 A000638. But not all of them occur as an automorphism group of a digraph.
%H A343592 Peter Dolland, <a href="/A343592/a343592.pdf">Digraph Symmetry Tables for n = 3..6</a>
%H A343592 Götz Pfeiffer, <a href="http://schmidt.nuigalway.ie/subgroups">Subgroups</a>. [broken link]
%e A343592 The four symmetry types of the digraphs with 3 nodes are represented by:
%e A343592 1.) {}, the empty graph, has together with the full graph the automorphism group S_3 (as subgroup of S_3) as symmetry type.
%e A343592 2.) {(1,2)} has together with 6 other digraphs the trivial automorphism group {id} as symmetry type. This digraph class is called asymmetric. Their values are given by A051504.
%e A343592 3.) {(1,2),(2,1)} has together with 5 other digraphs the automorphism group containing id and a transposition (so it is C_2 as the subgroup of S_3) as symmetry type.
%e A343592 4.) {(1,2),(2,3),(3,1)} has as the only digraph with three nodes the automorphism group C_3 as symmetry type. As a consequence it has to be self-complementary.
%e A343592 The total of the sizes of the symmetry type classes yields the number of digraphs A000273. Here: 2+7+6+1 = 16 = A000273(3).
%e A343592 Note, that for n > 3 there may be different symmetry types with isomorphic automorphism groups. For n=4 both {(1,2)} and {(1,2),(3,4)} have C_2 as automorphism group, but they are different as permutation group.
%Y A343592 Cf. A000273, A000638, A051504, A053763, A000595.
%K A343592 nonn,more
%O A343592 1,2
%A A343592 _Peter Dolland_, Apr 21 2021