An equality for balanced digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918211034808320 |
|---|---|
| author | Grinberg, Darij Liber, Benjamin |
| author_facet | Grinberg, Darij Liber, Benjamin |
| contents | 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). Moreover, this result can be generalized even further, replacing "contain no cycles" with "have a given set of cycles". |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_22388 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An equality for balanced digraphs Grinberg, Darij Liber, Benjamin Combinatorics 05C20, 05C45 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). Moreover, this result can be generalized even further, replacing "contain no cycles" with "have a given set of cycles". |
| title | An equality for balanced digraphs |
| topic | Combinatorics 05C20, 05C45 |
| url | https://arxiv.org/abs/2507.22388 |