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

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