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

---

REFERENCES

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

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength