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