There are two distinct notions of connectivity in a directed graph. A directed graph is weakly connected if there is an undirected path between any pair of vertices, and strongly connected if there is a directed path between every pair of vertices (Skiena 1990, p. 173). The following tables summarized the number of weakly and strongly connected digraphs on , 2, ... nodes. The 8 weakly but not strongly connected digraphs on three nodes are illustrated above.
Connected Digraph
See also
Connected Graph, Directed Graph, Strongly Connected Digraph, Weakly Connected DigraphExplore with Wolfram|Alpha
References
Skiena, S. "Strong and Weak Connectivity." §5.1.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 172-174, 1990.Sloane, N. J. A. Sequences A003085/M2067, A035512, and A056988 in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
Connected DigraphCite this as:
Weisstein, Eric W. "Connected Digraph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConnectedDigraph.html