A343592 Number of symmetry types of digraphs with n nodes.

1, 2, 4, 9, 14, 36

Offset: 1

Author

Peter Dolland, Apr 21 2021

Keywords

• nonn
• more

Comments

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.

Examples

			The four symmetry types of the digraphs with 3 nodes are represented by:
1.) {}, the empty graph, has together with the full graph the automorphism group S_3 (as subgroup of S_3) as symmetry type.
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.
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.
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.
The total of the sizes of the symmetry type classes yields the number of digraphs A000273. Here: 2+7+6+1 = 16 = A000273(3).
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.
		

Links

• Peter Dolland, Digraph Symmetry Tables for n = 3..6
• Götz Pfeiffer, Subgroups. [broken link]

Crossrefs

Cf. A000273, A000638, A051504, A053763, A000595.