The Tutte polynomial of a graph G is a two-variable polynomial that records much information on G. In particular, different evaluations at integers provide the number of spanning trees, forests (acyclic spanning subgraphs), and acyclic orientations of G. We estimate these values when G is an n× n square grid so as to deduce refined upper and lower bounds for the numbers of forests and acyclic orientations on such grids.
.8cm
p(G;0) 0 p(G;1) 1 if G is empty p(G;1) 0 if G contains an edge p(G;2) 2^{k(G)} if G is bipartite p(G;2) 0 if G is not bipartite |p(G;-1)| # of acyclic orientations [4]
T(G;1,1) # of spanning trees T(G;2,1) # of forests T(G;1,2) # of connected subgraphs T(G;2,0) # of acyclic orientations [4] T(G;1,0) # of ac. or. with a single source T(G;0,2) # of totally cyclic orientations
Table 1: Special evaluations of the chromatic (left) and Tutte (right) polynomials.
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.