The Tutte Polynomial of a Graph, Depth-first Search

Abstract

One of the most important numerical quantities that can be computed from a graph $G$ is the two-variable Tutte polynomial. Specializations of the Tutte polynomial count various objects associated with $G$, e.g., subgraphs, spanning trees, acyclic orientations, inversions and parking functions. We show that by partitioning certain simplicial complexes related to $G$ into intervals, one can provide combinatorial demonstrations of these results. One of the primary tools for providing such a partition is depth-first search.