Enumeration of digraphs with a given automorphism group

摘要

Four methods are described for enumerating digraphs with a given automorphism group: (1) a generating-function method based on subduced cycle indices, (2) a generating-function method based on partial cycle indices, (3) a method based on the elementary superposition theorem, and (4) a method based on the partial superposition theorem. All of these methods are based on the concept of unit subduced cycle indices and construct a set of versatile tools for combinatorial enumeration. They are applied to the enumeration of five-vertex digraphs with a given automorphism group. The table of marks and its inverse for the symmetric group of degree 5 are recalled. The table of USCIs of this roup is obtained.