Skip to Main content Skip to Navigation
Journal articles

Activity preserving bijections between spanning trees and orientations in graphs

Emeric Gioan 1, 2 Michel Las Vergnas 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 C&O - Equipe combinatoire et optimisation
IMJ-PRG - Institut de Mathématiques de Jussieu - Paris Rive Gauche
Abstract : The main results of the paper are two dual algorithms bijectively mapping the set of spanning trees with internal activity 1 and external activity 0 of an ordered graph onto the set of acyclic orientations with adjacent unique source and sink. More generally, these algorithms extend to an activity-preserving correspondence between spanning trees and orientations. For certain linear orderings of the edges, they also provide a bijection between spanning trees with external activity 0 and acyclic orientations with a given unique sink. This construction uses notably an active decomposition for orientations of a graph which extends the notion of components for acyclic orientations with unique given sink.
Complete list of metadata
Contributor : Emeric Gioan <>
Submitted on : Wednesday, June 13, 2007 - 11:44:13 PM
Last modification on : Monday, November 30, 2020 - 5:32:04 PM



Emeric Gioan, Michel Las Vergnas. Activity preserving bijections between spanning trees and orientations in graphs. Discrete Mathematics, Elsevier, 2005, 298 (1-3), pp.169-188. ⟨10.1016/j.disc.2005.04.010⟩. ⟨lirmm-00154519⟩



Record views