TOPICS

# 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 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).

Root Vertex, Rooted Tree

## Explore with Wolfram|Alpha

More things to try:

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

Rooted Graph

## Cite this as:

Weisstein, Eric W. "Rooted Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RootedGraph.html