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
| 👁 r_1 | 👁 = | 👁 1 |
(7)
|
| 👁 r_2 | 👁 = | 👁 1+x |
(8)
|
| 👁 r_3 | 👁 = | 👁 1+2x+2x^2+x^3 |
(9)
|
| 👁 r_4 | 👁 = | 👁 1+2x+4x^2+6x^3+4x^4+2x^5+x^6. |
(10)
|
This gives the array of rooted graphs on 👁 p
nodes with 👁 q
edges as illustrated in the following table (OEIS A070166).
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 TreeExplore 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."Referenced on Wolfram|Alpha
Rooted GraphCite this as:
Weisstein, Eric W. "Rooted Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RootedGraph.html