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

			(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	{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
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, , , ,

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength