Directed Acyclic Graph - Enumeration

Enumeration

The graph enumeration problem of counting directed acyclic graphs was studied by Robinson (1973). The number of DAGs on n labeled nodes, for n = 1, 2, 3, ..., is

1, 3, 25, 543, 29281, 3781503, ... (sequence A003024 in OEIS).

These numbers may be computed by the recurrence relation

Eric W. Weisstein conjectured, and McKay et al. (2004) proved, that the same numbers count the (0,1) matrices in which all eigenvalues are positive real numbers. The proof is bijective: a matrix A is an adjacency matrix of a DAG if and only if the eigenvalues of the (0,1) matrix A + I are positive, where I denotes the identity matrix.