Enumerating Degree Sequences in Digraphs and a Cycle-Cocycle Reversing System - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue European Journal of Combinatorics Année : 2007

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

Emeric Gioan

Résumé

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.

Dates et versions

lirmm-00154515 , version 1 (13-06-2007)

Identifiants

Citer

Emeric Gioan. Enumerating Degree Sequences in Digraphs and a Cycle-Cocycle Reversing System. European Journal of Combinatorics, 2007, 28 (4), pp.1351-1366. ⟨10.1016/j.ejc.2005.11.006⟩. ⟨lirmm-00154515⟩
72 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More