Activity preserving bijections between spanning trees and orientations in graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Discrete Mathematics Année : 2005

Activity preserving bijections between spanning trees and orientations in graphs

Résumé

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.

Dates et versions

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

Identifiants

Citer

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

Altmetric

Partager

More