Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 1 min ago
PreprintarXiv licencearXiv

Extremal arborescences in graph orientations

  • Jianing Liu
  • Zhijun Xu
Open at sourcePDFDOICite

Abstract

In this paper, we study the extremal number of arborescences over orientations of a fixed graph. We prove that every alternating orientation of a plane Eulerian multigraph minimizes the rooted arborescence count among its Eulerian orientations. We also prove that every tournament of odd order maximizing the total number of arborescences is regular, and hence Eulerian. These results resolve Conjectures 5.1 and 5.4 of Bandekar et al. We further establish upper bounds for arborescence counts in orientations of complete bipartite graphs and characterize the orientations attaining them.

Related

  1. A general theorem in spectral extremal graph theory
    John Byrne, Dheer Noal Desai, Michael Tait
    Transactions of the American Mathematical SocietyPeer-reviewedLicence not statedFull text24 citedCombinatorics & discrete mathematicsGeometry & topologyOpenAlex
  2. An explicit bound on the extremal function for complete graph minors
    David R. Wood
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Extremal Lin--Lu--Yau Curvature: Graph Density, Girth, and Short Cycles
    Qing Xia
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Spectral extremal problems on 1-planar graphs without Friendship graph
    Jiamin Li, Dan Li, Yuanyuan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Sharp Born--Infeld Sobolev inequality and extremal functions on the lattice graph ℤN
    Chao Ji, Kai Sheng
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{liu2026extremal,
  title = {{Extremal arborescences in graph orientations}},
  author = {Jianing Liu and Zhijun Xu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.25886},
  eprint = {2610.25886},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.25886},
}
RIS
TY  - UNPB
TI  - Extremal arborescences in graph orientations
AU  - Jianing Liu
AU  - Zhijun Xu
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.25886
UR  - https://arxiv.org/abs/2610.25886
AB  - In this paper, we study the extremal number of arborescences over orientations of a fixed graph. We prove that every alternating orientation of a plane Eulerian multigraph minimizes the rooted arborescence count among its Eulerian orientations. We also prove that every tournament of odd order maximizing the total number of arborescences is regular, and hence Eulerian. These results resolve Conjectures 5.1 and 5.4 of Bandekar et al. We further establish upper bounds for arborescence counts in orientations of complete bipartite graphs and characterize the orientations attaining them.
ER  -