Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings (Q1010839): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:53, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings |
scientific article |
Statements
Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings (English)
0 references
7 April 2009
0 references
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.
0 references
Tutte polynomial
0 references