The TuttePolynomial command returns a bivariate polynomial in x and y when x and y are variables or the evaluation of the bivariate polynomial when x or y are values.  The computation of the Tutte polynomial is NP-hard.

The Tutte polynomial, T(G;x,y), is a generalization of the chromatic polynomial and is defined as follows:

If e is a loop T(G;x,y) = y*T(G-e;x,y)

If e is a bridge (isthmus) then T(G;x,y) = x*T(G-e;x,y)

If e is not a bridge nor a loop then T(G;x,y) = T(G-e;x,y)+T(G/e;x,y)

G-e and G/e are the graph G with e removed and with e contracted, respectively.

ChromaticPolynomial, FlowPolynomial and RankPolynomial are all evaluations and functions of the Tutte polynomial.

The ChromaticPolynomial command returns a polynomial, P(G,t), which is the number of proper vertex colorings of G using no more than t colors, where t is a nonnegative integer.

The following two relations determine P(G,t):

If G contains a loop (not possible in current version of GraphTheory) then P'(G,t) = 0

If G contains no loop and e is an edge of G then P(G,t) = P(G-e,t) - P(G/e,t) where G-e is G with e removed and G/e is G with e contracted.

P(G,t) has been determined for certain classes of graphs. Fast codes for the special cases for the complete graph, its complement, trees and cycles have been included in the command.

The FlowPolynomial command returns a polynomial in x when x is a variable or the evaluation of the polynomial when x is a value. The value of this polynomial at a positive integer k gives the number of nowhere-zero flows on G with edge labels chosen from the integers modulo k.

The flow polynomial, Q(G;x), for a graph G with n vertices, m edges, and k connected components, can be expressed in terms of the Tutte polynomial, T(G;x,y), as follows:

Q(G;x) = (-1)^(m-n+k)*T(G;0,1-x)

The RankPolynomial command returns a bivariate polynomial in x and y when x and y are variables or the evaluation of the polynomial when x or y are values.

S(G;x,y) = T(G;x+1,y+1) where S(G;x,y) is the rank polynomial of G.

The AcyclicPolynomial command returns a polynomial in x when x is a variable or the evaluation of the polynomial when x is a value. The value of this polynomial at a value 0 <= p <= 1 gives the probability that G is acyclic when each edge operates with probability p.  It is function of T(G,x,1).

References

Modern graph theory, by Béla Bollobás, Graduate Texts in Mathematics, vol. 184, Springer, New York, 1998.