TOPICS
Search

Weakly Connected Digraph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
WeaklyConnectedDigraphs

A weakly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in some direction (i.e., not necessarily in the direction they point). In a weakly connected digraph with at least two nodes, every graph vertex therefore has positive outdegree or positive indegree. The numbers of nonisomorphic simple weakly connected digraphs on n=1, 2, ... nodes are 1, 2, 13, 199, 9364, ... (OEIS A003085).

See also

Connected Digraph, Strongly Connected Digraph, Weakly Connected Component

Explore with Wolfram|Alpha

References

Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 218, 1973.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. Sequence A003085/M2067 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Weakly Connected Digraph

Cite this as:

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

Subject classifications