Rooted Graph
المؤلف:
Cameron, P. J
المصدر:
"Sequences Realized by Oligomorphic Permutation Groups." J. Integer Seqs. 3
الجزء والصفحة:
...
8-5-2022
2453
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 ![<span style=]()
{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
Plugging in 
gives the counting polynomials
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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
