TOPICS
Search

Strongly Connected Digraph


StronglyConnectedDigraphs

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 n=1, 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].


See also

Connected Digraph, Strongly Connected Component, Weakly Connected Digraph

Explore with Wolfram|Alpha

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

Referenced on Wolfram|Alpha

Strongly Connected Digraph

Cite this as:

Weisstein, Eric W. "Strongly Connected Digraph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/StronglyConnectedDigraph.html

Subject classifications