Logo image
Back
An Equality for Balanced Digraphs
Journal article   Open access   Peer reviewed

An Equality for Balanced Digraphs

Darij Grinberg and Benjamin Liber
The Electronic journal of combinatorics, v 33(3), P3.19
17 Jul 2026
DOI: https://doi.org/10.37236/14616
Featured in Collection :   Drexel's Newest Publications
url
https://doi.org/10.37236/14616View
Published, Version of Record (VoR) Open CC BY V4.0

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 of$s$ . This generalizes known facts about spanning arborescences, acyclic orientations and maximal acyclic subdigraphs (or, equivalently, minimum feedback arc sets). Moreover, this result can be generalized even further, replacing "contain no cycles" with "have a given set of cycles".

Metrics

1 Record Views

Details

Logo image