TOPICS
Search

Connected Digraph


ConnectedDigraphs

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 n=1, 2, ... nodes. The 8 weakly but not strongly connected digraphs on three nodes are illustrated above.

connectivityOEIScounts
weakly connectedA0030851, 2, 13, 199, 9364, ...
strongly connectedA0355121, 1, 5, 83, 5048, 1047008, ...
weakly but not stronglyA0569880, 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 Web Resource. https://mathworld.wolfram.com/ConnectedDigraph.html

Subject classifications