Simple Directed Graph

 

A simple directed graph is a directed graph having no multiple edges or graph loops (corresponding to a binary adjacency matrix with 0s on the diagonal). The number of simple directed graphs of  nodes for , 2, ... are 1, 3, 16, 218, 9608, ... (OEIS A000273), which is given by NumberOfDirectedGraphs[n] in the Wolfram Language package Combinatorica` . The directed graphs on  nodes can be enumerated as ListGraphs[n, Directed] in the Wolfram Language package Combinatorica` .

A simple directed graph on  nodes may have between 0 and  edges. The number of simple directed graphs on  nodes with  edges can be given by NumberOfDirectedGraphs[n, m] in the Wolfram Language package Combinatorica` . The triangles of graphs counts on  nodes (rows) with  edges (columns) is given below (OEIS A052283).

	, 1, 2, ...
1	1
2	1, 1, 1
3	1, 1, 4, 4, 4, 1, 1
4	1, 1, 5, 13, 27, 38, 48, 38, 27, 13, 5, 1, 1

A complete graph in which each edge is bidirected is called a complete directed graph. A directed graph having no symmetric pair of directed edges (i.e., no bidirected edges) is called an oriented graph. A complete oriented graph (i.e., a directed graph in which each pair of nodes is joined by a single edge having a unique direction) is called a tournament.

A polynomial

(1)

that enumerates the number of distinct simple directed graphs with  nodes (where  is the number of directed graphs on  nodes with  edges) can be found by application of the Pólya enumeration theorem. This gives the counting polynomial for the number of directed graphs with  points as

(2)

where  is the reduced ordered pair group which acts on the 2-subsets of {1,2,...,p}" src="https://mathworld.wolfram.com/images/equations/SimpleDirectedGraph/Inline18.svg" style="height:22px; width:95px" />, given by

(3)

(Harary 1994, p. 186). Here,  is the floor function,  is a binomial coefficient, LCM is the least common multiple, GCD is the greatest common divisor, the sum  is over all exponent vectors of the cycle index, and  is the coefficient of the term with exponent vector  in . The first few cycle indices  are

			(4)
			(5)
			(6)
			(7)

Setting  gives the generating functions for the number of directed graphs on  nodes with  edges,

			(8)
			(9)
			(10)

---

REFERENCES

Harary, F. "Digraphs." Ch. 16 in Graph Theory. Reading, MA: Addison-Wesley, pp. 10, 186, and 198-211, 1994.

Sloane, N. J. A. Sequences A000273/M3032 and A052283 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