A simple directed graph is a directed graph having no multiple edges or graph loops (corresponding to a binary adjacency matrix with 0s on the diagonal). The number of simple directed graphs of nodes for , 2, ... are 1, 3, 16, 218, 9608, ... (OEIS A000273), which is given by NumberOfDirectedGraphs[n] in the Wolfram Language package Combinatorica` . The directed graphs on nodes can be enumerated as ListGraphs[n, Directed] in the Wolfram Language package Combinatorica` .
A simple directed graph on nodes may have between 0 and edges. The number of simple directed graphs on nodes with edges can be given by NumberOfDirectedGraphs[n, m] in the Wolfram Language package Combinatorica` . The triangles of graphs counts on nodes (rows) with edges (columns) is given 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 edge is bidirected is called a complete directed graph. A 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 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 2-subsets of , given by
(3)
|
(Harary 1994, p. 186). Here, is the floor function, is a binomial coefficient, LCM is the least common multiple, GCD is the greatest common divisor, the sum is over all exponent vectors of the cycle index, and is the coefficient of the term with exponent vector in . 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)
|