Preprint
An equality for balanced digraphs
30 Jul 2025
Abstract
Consider a directed multigraph $D$ that is balanced (i.e., at each vertex, the indegree equals the outdegree). Let $A$ be its set of arcs. Fix an integer $k$. Let $s$ be a vertex of $D$. We show that the number of $k$-element subsets $B$ of $A$ that contain no cycles but contain a path from each vertex to $s$ (we call them "$s$-convergences") is independent on $s$. This generalizes known facts about spanning arborescences, acyclic orientations and maximal acyclic subdigraphs (or, equivalently, minimum feedback arc sets).
Metrics
10 Record Views
Details
- Title
- An equality for balanced digraphs
- Creators
- Darij GrinbergBenjamin Liber
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991022068184104721