Activity preserving bijections between spanning trees and orientations in graphs

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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2005, 298 (1-3), pp.169-188. 〈http://www.lirmm.fr/~gioan〉. 〈10.1016/j.disc.2005.04.010〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00154519
Contributeur : Emeric Gioan <>
Soumis le : mercredi 13 juin 2007 - 23:44:13
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Citation

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. 〈http://www.lirmm.fr/~gioan〉. 〈10.1016/j.disc.2005.04.010〉. 〈lirmm-00154519〉

Partager

Métriques

Consultations de la notice

216