TOPICS
Search

Rank Polynomial


The rank polynomial R(x,y) of a general graph G is the function defined by

 R(x,y)=sum_(S subset= E(G))x^(r(S))y^(s(S)),
(1)

where the sum is taken over all subgraphs (i.e., edge sets) and the rank r(S) and co-rank s(S) of the subgraph S is given by

r(S)=n-c
(2)
s(S)=m-n+c
(3)

for a subgraph with n vertices, m edges, and c connected components (Biggs 1993, p. 73).

The rank polynomial is multiplicative over graph components, so for a graph G having connected components G_1, G_2, ..., the rank polynomial of G itself is given by

 R_G=R_(G_1)R_(G_2)....
(4)

It is given in terms of the Tutte polynomial T(x,y) as

 R(x,y)=x^(n-c)T(x^(-1)+1,y+1).
(5)

The chromatic polynomial pi(x) and rank polynomial of a general graph G with n vertices are related by

 pi(x)=x^nR(-x^(-1),-1)
(6)

(Biggs 1993, p. 75).

Trivially,

 R(x,x)=(x+1)^m,
(7)

where m 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 polynomialgraphs
1empty graph K^__n
1+x(3,2), (4,2), (5,2), (6,2), (7,2), (8,2), path graph P_2
1+3x+3x^2+x^2ytriangle graph, (4,6), (5,8), (6,10), (7,12), (8,14)
(1+x)^2(4,3), (5,3), (5,6), (6,3), (7,3), (7,8), (8,3), (8,9), (2,6)-fiveleaper graph, (4,5)-fiveleaper graph, (2,3)-knight graph, 2-ladder rung graph, path graph P_3
(1+x)^3claw graph, (5,4), (5,7), (5,9), (6,4), (6,8), (6,11), (7,4), (7,9), (7,13), (7,58), (8,4), (8,10), (8,15), (8,88), (3,6)-fiveleaper graph, 3-ladder rung graph, path graph P_4
(1+x)(1+3x+3x^2+x^2y)paw graph, (5,10), (5,20), (6,12), (6,37), (7,14), (7,60), (8,16), (8,91)
1+4x+6x^2+4x^3+x^3ysquare graph, C_4, (5,14), (6,22), (7,30), (8,38)
1+5x+10x^2+8x^3+2x^2y+5x^3y+x^3y^2diamond graph, (5,15), (6,23), (7,31), (8,39)
1+6x+15x^2+16x^3+4x^2y+15x^3y+6x^3y^2+x^3y^3tetrahedral graph, (5,24), (6,58), (7,114), (8,199)

See also

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

Explore with Wolfram|Alpha

WolframAlpha

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.

Referenced on Wolfram|Alpha

Rank Polynomial

Cite this as:

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

Subject classifications