Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00154515
Contributor : Emeric Gioan <>
Submitted on : Wednesday, June 13, 2007 - 11:04:29 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Identifiers

  • 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. ⟨lirmm-00154515⟩

Share

Metrics

Record views

175