Enumerating Degree Sequences in Digraphs and a Cycle-Cocycle Reversing System - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles European Journal of Combinatorics Year : 2007

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

Emeric Gioan

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.

Dates and versions

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

Identifiers

Cite

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⟩
73 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More