Enumerating Degree Sequences in Digraphs and a Cycle-Cocycle Reversing System

Emeric Gioan 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We give some new enumerations of indegree sequences of orientations of a graph using the Tutte polynomial. Then we introduce some discrete dynamical systems in digraphs consisting in reversing cycles, cocycles, or both, which extend the edge firing game (reversing sinks) by considering all orientations (reversing cocycles) and by introducing duality (reversing cycles). We show that indegree sequences can represent the configurations of these systems, and we enumerate equivalence classes of these systems. In particular, concerning the cycle-cocyle reversing system, we show that its configurations are in bijection with indegree sequences of orientations having a given vertex (quasi-sink of the system) reachable from any other. We also briefly discuss its generalization to oriented matroids, and relate structural and enumerative properties of its configurations to those of the sandpile model or chip firing game.
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2007, 28 (4), pp.1351-1366. 〈http://www.lirmm.fr/~gioan〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00154515
Contributeur : Emeric Gioan <>
Soumis le : mercredi 13 juin 2007 - 23:04:29
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00154515, version 1

Collections

Citation

Emeric Gioan. Enumerating Degree Sequences in Digraphs and a Cycle-Cocycle Reversing System. European Journal of Combinatorics, Elsevier, 2007, 28 (4), pp.1351-1366. 〈http://www.lirmm.fr/~gioan〉. 〈lirmm-00154515〉

Partager

Métriques

Consultations de la notice

105