Rooted Graph -- From Wolfram MathWorld

Home » What Does The Root Graph Mean » Rooted Graph -- From Wolfram MathWorld

Maybe your like

RootedGraphs

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

r_p(x)=Z((S_1+S_(p-1))^((2)),1+x), (1)

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

Z((S_1+S_0)^((2)))=1 (2)
Z((S_1+S_1)^((2)))=x_1 (3)
Z((S_1+S_2)^((2)))=1/2x_1^3+1/2x_2x_1 (4)
Z((S_1+S_3)^((2)))=1/6x_1^6+1/2x_2^2x_1^2+1/3x_3^2 (5)
Z((S_1+S_4)^((2)))=1/(24)x_1^(10)+1/4x_2^3x_1^4+1/8x_2^4x_1^2+1/3x_3^3x_1+1/4x_2x_4^2. (6)

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

pq=0, 1, 2, ...
11
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).

Tag » What Does The Root Graph Mean