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