| Tutte Polynomials in Square Grids (2007) | |||||||||||||||
Abstract | |||||||||||||||
| The Tutte polynomial of a graph G is a two-variable polynomial that records much information on G. In particular, dierent 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 rened upper and lower bounds for the numbers of forests and acyclic orientations on such grids. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||