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

rooted tree | root vertex