The rank polynomial of a general graph is the function defined by
(1)
|
where the sum is taken over all subgraphs (i.e., edge sets) and the rank and co-rank of the subgraph is given by
(2)
| |||
(3)
|
for a subgraph with vertices, edges, and connected components (Biggs 1993, p. 73).
The rank polynomial is multiplicative over graph components, so for a graph having connected components , , ..., the rank polynomial of itself is given by
(4)
|
It is given in terms of the Tutte polynomial as
(5)
|
The chromatic polynomial and rank polynomial of a general graph with vertices are related by
(6)
|
(Biggs 1993, p. 75).
Trivially,
(7)
|
where is the number of edges of the graph (Biggs 1993, p. 74).
The following table summarizes rank polynomials for some common classes of graphs.
graph | rank polynomial |
banana tree | |
book graph | |
centipede graph | |
cycle graph | |
gear graph | |
ladder rung graph | |
pan graph | |
path graph | |
star graph | |
sunlet graph |
The following table summarizes recurrence equations for rank polynomials of common classes of graphs.
graph | recurrence |
book graph | |
cycle graph | |
gear graph | |
helm graph | |
ladder graph | |
pan graph | |
sunlet graph | |
wheel graph |
Nonisomorphic graphs do not necessarily have distinct rank polynomials. The following table summarizes some co-rank graphs.
rank polynomial | graphs |
1 | empty graph |
, , , , , , path graph | |
triangle graph, , , , , | |
, , , , , , , , -fiveleaper graph, -fiveleaper graph, -knight graph, 2-ladder rung graph, path graph | |
claw graph, , , , , , , , , , , , , , , -fiveleaper graph, 3-ladder rung graph, path graph | |
paw graph, , , , , , , , ) | |
square graph, , , , , | |
diamond graph, , , , | |
tetrahedral graph, , , , |