Acyclic Digraph
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 equation
 |
with 
(Harary and Palmer 1973, p. 19;
Robinson 1973, pp. 239-273).
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 
-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."
Weisstein, Eric W. "Acyclic Digraph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AcyclicDigraph.html
Contact the MathWorld Team
7 on 3 4-sided dice
