Skip to Main content Skip to Navigation
Journal articles

The active bijection for graphs

Emeric Gioan 1 Michel Las Vergnas 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The active bijection forms a package of results studied by the authors in a series of papers in oriented matroids. The present paper is intended to state the main results in the particular case, and more widespread language, of graphs. We study fundamental properties of (directed) graphs on a linearly ordered set of edges. The central result is that, for a directed graph on a linearly ordered set of edges, we determine in a canonical way one particular spanning tree, which we call the active spanning tree and which has important properties. For any graph on a linearly ordered set of edges, this yields a surjective mapping from orientations onto spanning trees, which preserves activities (for orientations in the sense of Las Vergnas, for spanning trees in the sense of Tutte), as well as some partitions (or filtrations) of the edge set associated with orientations and spanning trees. This yields a canonical bijection between classes of orientations and spanning trees, as well as a refined bijection between all orientations and edge subsets, containing various notable bijections, for instance: between orientations in which smallest edges of cycles and cocycles have a fixed orientation and spanning trees; or between acyclic orientations and no-broken-circuit subsets. Several constructions of independent interest are involved. The basic case concerns bipolar orientations, which are in bijection with their fully optimal spanning trees, as proved in a previous paper. We give a canonical decomposition of a directed graph on a linearly ordered set of edges into acyclic/cyclic bipolar directed graphs. Considering all orientations of a graph, we obtain an expression of the Tutte polynomial in terms of products of beta invariants of minors, an important partition of the set of orientations into activity classes, and a simple expression of the Tutte polynomial using four orientation-activity parameters. We derive a similar decomposition theorem for spanning trees. We also provide a general deletion/contraction framework for these bijections and relatives.
Complete list of metadatas

Cited literature [48 references]  Display  Hide  Download
Contributor : Emeric Gioan <>
Submitted on : Friday, January 17, 2020 - 1:58:52 PM
Last modification on : Friday, January 17, 2020 - 2:19:26 PM


Files produced by the author(s)




Emeric Gioan, Michel Las Vergnas. The active bijection for graphs. Advances in Applied Mathematics, Elsevier, 2019, 104, pp.165-236. ⟨10.1016/j.aam.2018.11.001⟩. ⟨lirmm-01996135⟩



Record views


Files downloads