Strongly Connected Digraph

A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point. The nodes in a strongly connected digraph therefore must all have indegree of at least 1. The numbers of nonisomorphic simple strongly connected digraphs on , 2, ... nodes are 1, 1, 5, 83, 5048, 1047008, ... (OEIS A035512).

A directed graph can be tested to see if it is strongly connected using ConnectedGraphQ[g].

REFERENCES

Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 218, 1973.

Liskovec, V. A. "A Contribution to the Enumeration of Strongly Connected Digraphs." Dokl. AN BSSR 17, 1077-1080, 1973.

Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.

Skiena, S. "Strong and Weak Connectivity." §5.1.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 94 and 172-174, 1990.

Sloane, N. J. A. Sequence A035512 in "The On-Line Encyclopedia of Integer Sequences."