TOPICS
Search

Rank Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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.

graphrank polynomial
banana tree(1+x)^(nk)
book graph S_(n+1) square P_2([1+3x(x+1)]^n(y-x)+x(y+1){1+x[3+x(3+y)]}^n)/y
centipede graph(x+1)^(2n-1)
cycle graph C_nx^(n-1)(y-x)+(x+1)^n
gear graph(x[x^2(y+4)+3x+1-s]^n+x[x^2(y+4)+3x+1+s]^n-2^(n+1)x^(2n+1)+2^nyx^(2n))/x
ladder rung graph nP_2(1+x)^n
pan graphx^(n-1)(y-x)+(x+1)^(n+1)
path graph P_n(1+x)^(n-1)
star graph S_n(1+x)^n
sunlet graph C_n circledot K_1(1+x)^n[(1+x)^n+x^(n-1)(y-x)]

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

graphrecurrence
book graph S_(n+1) square P_2p_n=(x^2y+6x^2+6x+2)p_(n-1)-(3x^2+3x+1)(x^2y+3x^2+3x+1)p_(n-2)
cycle graph C_np_n=(2x+1)p_(n-1)-x(x+1)p_(n-2)
gear graphp_n=(1+3x+5x^2+x^2y)p_(n-1)-x^2(2+5x+5x^2+y+2xy+2x^2y)p_(n-2)+(x^4(1+x)^2(1+y))p_(n-3)
helm graphp_n=(x+1)(xy+4x+1)p_(n-1)-x(2x+1)(x+1)^2(y+2)p_(n-2)+x^2(x+1)^4(y+1)p_(n-3)
ladder graph L_np_n=(1+3x+4x^2+x^2y)p_(n-1)-x^2(x+1)^2(y+1)p_(n-2)
pan graphp_n=(2x+1)p_(n-1)-x(x+1)p_(n-2)
sunlet graph C_n circledot K_1p_n=(x+1)(2x+1)p_(n-1)-x(x+1)^3p_(n-2)
wheel graph W_np_n=(1+4x+xy)p_(n-1)-x(2x+1)(y+2)p_(n-2)+x^2(x+1)(y+1)p_(n-3)

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

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 Resource. https://mathworld.wolfram.com/RankPolynomial.html

Subject classifications