TOPICS
Search

Acyclic Digraph


AcyclicDigraphs

An acyclic digraph is a directed graph containing no directed cycles, also known as a directed acyclic graph or a "DAG." Every finite acyclic digraph has at least one node of outdegree 0. The numbers of acyclic digraphs on n=1, 2, ... vertices are 1, 2, 6, 31, 302, 5984, ... (OEIS A003087).

The numbers of labeled acyclic digraphs on n=1, 2, ... nodes are 1, 3, 25, 543, 29281, ... (OEIS A003024). Weisstein's conjecture proposed that positive eigenvalued (0,1)-matrices were in one-to-one correspondence with labeled acyclic digraphs on n nodes, and this was subsequently proved by McKay et al. (2004). Counts for both are therefore given by the beautiful recurrence equation

 a_n=sum_(k=1)^n(-1)^(k-1)(n; k)2^(k(n-k))a_(n-k)

with a_0=1 (Harary and Palmer 1973, p. 19; Robinson 1973, pp. 239-273).


See also

Forest, Hyperstring, Positive Eigenvalued Matrix, Simple Directed Graph, Weisstein's Conjecture

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 200, 1994.Harary, F. and Palmer, E. M. "Acyclic Digraph." §8.8 in Graphical Enumeration. New York: Academic Press, pp. 191-194, 1973.McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; and Wilf, H. "Acyclic Digraphs and Eigenvalues of (0,1)-Matrices." J. Integer Sequences 7, Article 04.3.3, 1-5, 2004. http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html.Robinson, R. W. "Counting Labeled Acyclic Digraphs." In New Directions in Graph Theory (Ed. F. Harary). New York: Academic Press, 1973.Robinson, R. W. "Counting Unlabeled Acyclic Digraphs." In Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference, held at the Royal Melbourne Institute of Technology, Aug. 24-26, 1976). Providence, RI: Amer. Math. Soc., pp. 28-43, 1976.Sloane, N. J. A. Sequence A003087/M1696 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Acyclic Digraph

Cite this as:

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

Subject classifications