TOPICS
Search

Simple Directed Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
SimpleDigraphs

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 n nodes for n=1, 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 n nodes can be enumerated as ListGraphs[n, Directed] in the Wolfram Language package Combinatorica` .

A simple directed graph on n nodes may have between 0 and n(n-1) edges. The number of simple directed graphs on n nodes with m edges can be given by NumberOfDirectedGraphs[n, m] in the Wolfram Language package Combinatorica` . The triangles of graphs counts on n nodes (rows) with m edges (columns) is given below (OEIS A052283).

nm=0, 1, 2, ...
11
21, 1, 1
31, 1, 4, 4, 4, 1, 1
41, 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

d_p(x)=sum_(q)d_(pq)x^q
(1)

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

d_p(x)=Z(S_p^([2]),1+x),
(2)

where S_p^([2]) is the reduced ordered pair group which acts on the 2-subsets of {1,2,...,p}, given by

Z(S_p^([2]))=1/(p!)sum_((j))(p!)/(product_(k=1)^(p)k^(j_k)j_k!)a_k^((k-1)j_k+2k(j_k; 2))product_(q=1)^pproduct_(r=q+1)^pa_(LCM(q,r))^(j_qj_rGCD(q,r))
(3)

(Harary 1994, p. 186). Here, |_x_| is the floor function, (n; m) is a binomial coefficient, LCM is the least common multiple, GCD is the greatest common divisor, the sum (j) is over all exponent vectors of the cycle index, and h_(j) is the coefficient of the term with exponent vector j_p in Z(S_p^([2])). The first few cycle indices Z(S_p^([2])) are

S_2^([2])=1/2a_1^2+1/2a_2
(4)
S_3^([2])=1/6a_1^6+1/2a_2^3+1/3a_3^2
(5)
S_4^([2])=1/(24)x_1^(12)+1/4x_2^5x_1^2+1/8x_2^6+1/3x_3^4+1/4x_4^3
(6)
S_5^([2])=1/(120)x_1^(20)+1/(12)x_2^7x_1^6+6/x_3^6x_1^2+1/8x_2^(10)+1/4x_4^5+1/5x_5^4+1/6x_2x_3^2x_6^2.
(7)

Setting a_n=1+x^n gives the generating functions for the number of directed graphs on n nodes with k edges,

d_1=x
(8)
d_2=x^2+x+1
(9)
d_3=x^6+x^5+4x^4+4x^3+4x^2+x+1.
(10)

See also

Acyclic Digraph, Directed Graph, Oriented Graph, Simple Graph, Strongly Connected Digraph, Tournament, Weakly Connected Digraph

Explore with Wolfram|Alpha

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."

Referenced on Wolfram|Alpha

Simple Directed Graph

Cite this as:

Weisstein, Eric W. "Simple Directed Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SimpleDirectedGraph.html

Subject classifications