Activity preserving bijections between spanning trees and orientations in graphs

DOI10.1016/j.disc.2005.04.010zbMath1070.05026OpenAlexW2075794743MaRDI QIDQ2566282

Emeric Gioan, Michel Las Vergnas

Publication date: 22 September 2005

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2005.04.010

zbMATH Keywords

AlgorithmTutte polynomialOrientationMatroidDirected graphSourceOriented matroidBijectionAcyclicSink

Mathematics Subject Classification ID

Trees (05C05) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Oriented matroids in discrete geometry (52C40)

Related Items (19)

On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids ⋮ Geometric bijections for regular matroids, zonotopes, and Ehrhart theory ⋮ Criterion for a graph to admit a good orientation in terms of leaf blocks ⋮ Enumerating degree sequences in digraphs and a cycle--cocycle reversing system ⋮ Fourientation activities and the Tutte polynomial ⋮ Fully Optimal Bases and the Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids ⋮ Computing the fully optimal spanning tree of an ordered bipolar directed graph ⋮ On the number of circuit-cocircuit reversal classes of an oriented matroid ⋮ Bases, reorientations, and linear programming, in uniform and rank-3 oriented matroids ⋮ The active bijection for graphs ⋮ Riemann-Roch theory for graph orientations ⋮ \(G\)-parking functions, acyclic orientations and spanning trees ⋮ GEOMETRIC BIJECTIONS FOR REGULAR MATROIDS, ZONOTOPES, AND EHRHART THEORY ⋮ Unnamed Item ⋮ A bijection for Eulerian-equivalence classes of totally cyclic orientations ⋮ Topological bijections for oriented matroids ⋮ The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: the fully optimal basis of a bounded region ⋮ A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements ⋮ ACYCLIC ORIENTATIONS ON THE SIERPINSKI GASKET

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orientability of matroids
• External and internal elements of a matroid basis
• A note on major sequences and external activity in trees
• The sand-pile model and Tutte polynomials
• Bases, reorientations, and linear programming, in uniform and rank-3 oriented matroids
• Bipolar orientations revisited
• Sinks in acyclic orientations of graphs
• The active bijection between regions and simplices in supersolvable arrangements of hyperplanes
• Acyclic orientations of graphs
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Partitions ofN-Space by Hyperplanes
• A Contribution to the Theory of Chromatic Polynomials
• Acyclic orientations and the chromatic polynomial

This page was built for publication: Activity preserving bijections between spanning trees and orientations in graphs