A connected digraph is a directed graph whose connectivity is interpreted in a weak or strong sense. It is weakly
connected if its underlying undirected graph
is connected, and strongly
connected if, for every ordered pair 
of distinct vertices,
there is a directed graph path from 
to 
(Skiena 1990, p. 173). The following table gives the
numbers of nonisomorphic simple
directed graphs on 
, 2, ... vertices, allowing
oppositely directed edges between a pair of vertices.
The 8 weakly but not strongly connected digraphs on three vertices
are illustrated above.
| connectivity | OEIS | counts |
| weakly connected | A003085 | 1, 2, 13, 199, 9364, ... |
| strongly
connected | A035512 | 1, 1, 5, 83, 5048, 1047008, ... |
| weakly
but not strongly | A056988 | 0, 1, 8, 116, 4316, 483835, ... |
See also
Connected Graph,
Directed Graph,
Strongly Connected Digraph,
Weakly Connected Digraph
Explore 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 Digraph
Cite this as:
Weisstein, Eric W. "Connected Digraph."
From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ConnectedDigraph.html
Subject classifications
