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

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

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

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