TOPICS
Search

Rank Matrix

If the rank polynomial R(x,y) of a graph G is given by sumrho_(rs)x^ry^s, then rho_(rs) is the number of subgraphs of G with rank r and co-rank s, and the matrix (rho_(rs)) is called the rank matrix of G.

For example, the rank matrix of the complete bipartite graph K_(3,3), which has rank polynomial

R(x,y)=1+9x+36x^2+84x^3+117x^4+81x^5+9x^3y +45x^4y+78x^5y+6x^4y^2+36x^5y^2+9x^5y^3+x^5y^4,
(1)

is given by

[1 ; 9 ; 36 ; 84 9 ; 117 45 6 ; 81 78 36 9 1]
(2)

(Biggs 1993, p. 73), and the rank matrix of the Petersen graph is

[1 ; 15 ; 105 ; 455 ; 1365 12 ; 2991 130 ; 4875 630 30 ; 5805 1725 240 15 ; 4680 2765 816 135 10 ; 2000 2172 1230 445 105 15 1]
(3)

(Godsil and Royle 2001, p. 356).

See also

Rank Polynomial

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, p. 73, 1993.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.

Referenced on Wolfram|Alpha

Rank Matrix

Cite this as:

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

Subject classifications