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 , 2, ... vertices are 1, 2, 6, 31, 302, 5984, ... (OEIS A003087).
The numbers of labeled acyclic digraphs on
, 2, ... nodes are 1, 3, 25, 543, 29281, ... (OEIS A003024).
Weisstein's conjecture proposed that positive eigenvalued -matrices were in one-to-one
correspondence with labeled acyclic digraphs on nodes, and this was subsequently proved by McKay et al.
(2004). Counts for both are therefore given by the beautiful recurrence
(Harary and Palmer 1973, p. 19; Robinson 1973, pp. 239-273).
See also Forest
Positive Eigenvalued Matrix
Explore with Wolfram|Alpha
References Harary, F. Reading, MA: Addison-Wesley, p. 200, 1994. Graph Theory. Harary,
F. and Palmer, E. M. "Acyclic Digraph." §8.8 in New York: Academic Press, pp. 191-194, 1973. Graphical
B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.;
and Wilf, H. "Acyclic Digraphs and Eigenvalues of -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 (Ed. F. Harary). New York: Academic Press,
Directions in Graph Theory Robinson, R. W. "Counting Unlabeled Acyclic Digraphs."
In Providence, RI: Amer.
Math. Soc., pp. 28-43, 1976. Combinatorial
Mathematics V: Proceedings of the Fifth Australian Conference, held at the Royal
Melbourne Institute of Technology, Aug. 24-26, 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 --A Wolfram Web Resource. MathWorld https://mathworld.wolfram.com/AcyclicDigraph.html