# zbMATH — the first resource for mathematics

Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings. (English) Zbl 1179.05048
Summary: We define a bijection between spanning subgraphs and orientations of graphs and explore its enumerative consequences regarding the Tutte polynomial. We obtain unifying bijective proofs for all the evaluations $$T_G(i,j),0\leq i,j \leq 2$$ of the Tutte polynomial in terms of subgraphs, orientations, outdegree sequences and sandpile configurations. For instance, for any graph $$G$$, we obtain a bijection between connected subgraphs (counted by $$T_G(1,2))$$ and root-connected orientations, a bijection between forests (counted by $$T_G(2,1))$$ and outdegree sequences and bijections between spanning trees (counted by $$T_G(1,1))$$, root-connected outdegree sequences and recurrent sandpile configurations. All our proofs are based on a single bijection $$\Phi$$ between the spanning subgraphs and the orientations that we specialize in various ways. The bijection$$\Phi$$ is closely related to a recent characterization of the Tutte polynomial relying on combinatorial embeddings of graphs, that is, on a choice of cyclic order of the edges around each vertex.

##### MSC:
 05C20 Directed graphs (digraphs), tournaments
Tutte polynomial
Full Text: