Read More
Date: 11-5-2022
1791
Date: 15-3-2022
1509
Date: 27-3-2022
1244
|
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
(2) |
|||
(3) |
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 | |
centipede graph | |
cycle graph | |
gear graph | |
ladder rung graph | |
pan graph | |
path graph | |
star graph | |
sunlet graph |
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, , , , |
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.
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|