EUVIMEDEUVIMED entdecken
Crossref

An Equality for Balanced Digraphs

Darij Grinberg, Benjamin Liber

The Electronic Journal of Combinatorics · 17.07.2026 · 33 (3)

DOI: 10.37236/14616 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 17.07.2026. Verfasst von Darij Grinberg und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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".

Zitieren

APA

Grinberg, D., & Liber, B. (2026). An Equality for Balanced Digraphs. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/14616

Vancouver

Grinberg D, Liber B. An Equality for Balanced Digraphs. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/14616

BibTeX
@article{Grinberg2026,
  author = {Grinberg, Darij and Liber, Benjamin},
  title = {An Equality for Balanced Digraphs},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {3},
  doi = {10.37236/14616}
}
Kostenlos starten →