Rank Polynomial
المؤلف:
Biggs, N. L
المصدر:
Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press
الجزء والصفحة:
...
20-4-2022
1817
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
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.
| graph |
rank polynomial |
| banana tree |
 |
book graph  |
![([1+3x(x+1)]^n(y-x)+x(y+1)<span style=]() {1+x[3+x(3+y)]}^n)/y" src="https://mathworld.wolfram.com/images/equations/RankPolynomial/Inline26.svg" style="height:33px; width:265px" /> |
| centipede graph |
 |
cycle graph  |
 |
| 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](https://mathworld.wolfram.com/images/equations/RankPolynomial/Inline30.svg) |
ladder rung graph  |
 |
| pan graph |
 |
path graph  |
 |
star graph  |
 |
sunlet graph  |
![(1+x)^n[(1+x)^n+x^(n-1)(y-x)]](https://mathworld.wolfram.com/images/equations/RankPolynomial/Inline39.svg) |
The following table summarizes recurrence equations for rank polynomials of common classes of graphs.
| graph |
recurrence |
book graph  |
 |
cycle graph  |
 |
| gear graph |
 |
| helm graph |
 |
ladder graph  |
 |
| pan graph |
 |
sunlet graph  |
 |
wheel graph  |
 |
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,  ,  ,  ,  |
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
