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 n nodes are isomorphic with the symmetric relations on n nodes. The counting polynomial for the number of rooted graphs with p points is


where S_1+S_(p-1) is the symmetric group S_(p-1) with an additional element {p} appended to each element, (S_1+S_(p-1))^((2)) is its pair group, and Z((S_1+S_(p-1))^((2))) the corresponding cycle index (Harary 1994, p. 186). The first few cycle indices are


Plugging in x_i=1+x^i gives the counting polynomials


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

pq=0, 1, 2, ...
21, 1
31, 2, 2, 1
41, 2, 4, 6, 4, 2, 1
51, 2, 5, 11, 17, 18, 17, 11, 5, 2, 1

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

See also

Root Vertex, Rooted Tree

Explore with Wolfram|Alpha


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

Referenced on Wolfram|Alpha

Rooted Graph

Cite this as:

Weisstein, Eric W. "Rooted Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications