TOPICS

# Rank Polynomial

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.

The following table summarizes recurrence equations for rank polynomials of common classes of graphs.

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

## See also

Chromatic Polynomial, Flow Polynomial, Rank Matrix, Reliability Polynomial, Tutte Polynomial

## Explore with Wolfram|Alpha

More things to try:

## References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 73, 97, and 101, 1993.Godsil, C. and Royle, G. "Rank Polynomial" and "Evaluations of the Rank Polynomial." §15.9-15.10 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 355-358, 2001.

Rank Polynomial

## Cite this as:

Weisstein, Eric W. "Rank Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RankPolynomial.html