Rooted Graph

 

A rooted graph is a graph in which one node is labeled in a special way so as to distinguish it from other nodes. The special node is called the root of the graph. The rooted graphs on  nodes are isomorphic with the symmetric relations on  nodes. The counting polynomial for the number of rooted graphs with  points is

(1)

where  is the symmetric group  with an additional element {p}" src="https://mathworld.wolfram.com/images/equations/RootedGraph/Inline6.svg" style="height:22px; width:24px" /> appended to each element,  is its pair group, and  the corresponding cycle index (Harary 1994, p. 186). The first few cycle indices are

			(2)
			(3)
			(4)
			(5)
			(6)

Plugging in  gives the counting polynomials

			(7)
			(8)
			(9)
			(10)

This gives the array of rooted graphs on  nodes with  edges as illustrated in the following table (OEIS A070166).

	, 1, 2, ...
1	1
2	1, 1
3	1, 2, 2, 1
4	1, 2, 4, 6, 4, 2, 1
5	1, 2, 5, 11, 17, 18, 17, 11, 5, 2, 1

Plugging in  into  then gives the numbers of rooted graphs on , 2, ... nodes as 1, 2, 6, 20, 90, 544, ... (OEIS A000666).

---

REFERENCES

Cameron, P. J. "Sequences Realized by Oligomorphic Permutation Groups." J. Integer Seqs. 3, #00.1.5, 2000.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 186, 1994.

Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 241, 1973.

Harary, F.; Palmer, E. M.; Robinson, R. W.; and Schwenk, A. J. "Enumeration of Graphs with Signed Points and Lines." J. Graph Theory 1, 295-308, 1977.

McIlroy, M. D. "Calculation of Numbers of Structures of Relations on Finite Sets." Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports. No. 17, Sept. 15, pp. 14-22, 1955.

Oberschelp, W. "Kombinatorische Anzahlbestimmungen in Relationen." Math. Ann. 174, 53-78, 1967.

Sloane, N. J. A. Sequences A000666/M1650 and A070166 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