Chip-firing game and a partial Tutte polynomial for Eulerian digraphs

Kévin Perrot¹ ; Trung Van Pham²

¹Aix Marseille Université, CNRS
²Vienna University of Technology, Austria.

The electronic journal of combinatorics, Tome 23 (2016) no. 1

Résumé

The Chip-firing game is a discrete dynamical system played on a graph, in which chips move along edges according to a simple local rule. Properties of the underlying graph are of course useful to the understanding of the game, but since a conjecture of Biggs that was proved by Merino López, we also know that the study of the Chip-firing game can give insights on the graph. In particular, a strong relation between the partial Tutte polynomial $T_G(1,y)$ and the set of recurrent configurations of a Chip-firing game (with a distinguished sink vertex) has been established for undirected graphs. A direct consequence is that the generating function of the set of recurrent configurations is independent of the choice of the sink for the game, as it characterizes the underlying graph itself. In this paper we prove that this property also holds for Eulerian directed graphs (digraphs), a class on the way from undirected graphs to general digraphs. It turns out from this property that the generating function of the set of recurrent configurations of an Eulerian digraph is a natural and convincing candidate for generalizing the partial Tutte polynomial $T_G(1,y)$ to this class. Our work also gives some promising directions of looking for a generalization of the Tutte polynomial to general digraphs.

Détail

DOI : 10.37236/3924

Classification : 91A43, 05C57, 91A46, 05C20, 05C31, 05C45
Mots-clés : chip-firing game, critical configuration, Eulerian digraph, feedback arc set, recurrent configuration, reliability polynomial, sandpile model, Tutte polynomial