Simple Directed Graph

 

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)

---

REFERENCES

Harary, F. "Digraphs." Ch. 16 in Graph Theory. Reading, MA: Addison-Wesley, pp. 10, 186, and 198-211, 1994.

Sloane, N. J. A. Sequences A000273/M3032 and A052283 in "The On-Line Encyclopedia of Integer Sequences."

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength