Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9513190 | Discrete Mathematics | 2005 | 20 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Emeric Gioan, Michel Las Vergnas,