Activity preserving bijections between spanning trees and orientations in graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Mathematics Year : 2005

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.

Dates and versions

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

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More