Simple Directed Graph

A simple directed graph is a directed graph having no multiple edges or graph loops (corresponding to an adjacency matrix with entries 0 or 1 and 0s on the diagonal). The number of nonisomorphic simple directed graphs of nodes for , 2, ... are 1, 3, 16, 218, 9608, ... (OEIS A000273).

A simple directed graph on nodes may have between 0 and edges. The number of simple directed graphs on nodes with edges gives the triangle of graph counts on nodes (rows) with edges (columns) shown below (OEIS A052283).

	, 1, 2, ...
1	1
2	1, 1, 1
3	1, 1, 4, 4, 4, 1, 1
4	1, 1, 5, 13, 27, 38, 48, 38, 27, 13, 5, 1, 1

A complete graph in which each graph edge is bidirected is called a complete digraph. A simple directed graph having no symmetric pair of directed edges (i.e., no bidirected edges) is called an oriented graph. A complete oriented graph (i.e., a directed graph in which each pair of nodes is joined by a single graph edge having a unique direction) is called a tournament.

A polynomial

(1)

that enumerates the number of distinct simple directed graphs with nodes (where is the number of directed graphs on nodes with edges) can be found by application of the Pólya enumeration theorem. This gives the counting polynomial for the number of directed graphs with points as

(2)

where is the reduced ordered pair group which acts on the ordered pairs of distinct elements of , given by

(3)

(Harary 1994, p. 186). Here, is a binomial coefficient, LCM is the least common multiple, GCD is the greatest common divisor, and the sum is over exponent vectors satisfying , where counts the cycles of length in a permutation of the symmetric group . The first few cycle indices are

			(4)
			(5)
			(6)
			(7)

Setting gives the generating functions for the number of directed graphs on nodes with edges,

			(8)
			(9)
			(10)