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 vertex of the graph.
Rooted simple graphs on 
nodes correspond to symmetric
relations on 
nodes. The counting polynomial for rooted simple graphs
with 
points, counted up to root-preserving
graph isomorphism, is
 |
(1)
|
where 
is the symmetric group 
acting on 
points with point 
fixed, 
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 |
Substituting 
into 
then gives the numbers of rooted graphs on 
, 2, ... nodes as 1, 2, 6, 20, 90, 544, ... (OEIS A000666).
