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 unlabeled acyclic digraphs
on vertices are 1, 2, 6, 31, 302, 5984, ... (OEIS
A003087 ).
The numbers of labeled acyclic digraphs on 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). For recurrence equation
with
See also Acyclic Orientation ,
Forest ,
Hyperstring ,
Positive
Eigenvalued Matrix ,
Simple Directed Graph ,
Weisstein's Conjecture
Explore with Wolfram|Alpha
References Harary, F. Graph Theory. Harary,
F. and Palmer, E. M. "Acyclic Digraph." §8.8 in Graphical
Enumeration. McKay,
B. D.; Oggier, F. E.; Royle, G. F.; Sloane, N. J. A.; Wanless,
I. M.; and Wilf, H. "Acyclic Digraphs and Eigenvalues of J. Integer Sequences 7 ,
Article 04.3.3, 1-5, 2004. https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html . Robinson,
R. W. "Counting Labeled Acyclic Digraphs." In New
Directions in Graph Theory 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. https://doi.org/10.1007/BFb0069178 . Sloane,
N. J. A. Sequences A003024 and 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 https://mathworld.wolfram.com/AcyclicDigraph.html
Subject classifications More... Less...
,
2, ... vertices are 1, 2, 6, 31, 302, 5984, ... (OEIS
A003087).
, 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). For 
, counts for both are therefore given by the beautiful
recurrence equation
(Harary and Palmer 1973, p. 19; Robinson 1973, pp. 239-273).
-Matrices." J. Integer Sequences 7,
Article 04.3.3, 1-5, 2004.