DAG | digraph | directed acyclic graph

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).

forest | hyperstring | positive eigenvalued matrix | simple directed graph | Weisstein's conjecture