EUVIMEDEUVIMED entdecken
Crossref

Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2

Jørgen Bang‐Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo

Journal of Graph Theory · 2022-06 · 100 (2) · 294-314

DOI: 10.1002/jgt.22779 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 06.12.2021. Verfasst von Jørgen Bang‐Jensen und 3 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 14 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We prove that every digraph of independence number at most 2 and arc‐connectivity at least 2 has an out‐branching and an in‐branching which are arc‐disjoint (we call such branchings a good pair ). This is best possible in terms of the arc‐connectivity as there are infinitely many strong digraphs with independence number 2 and arbitrarily high minimum in‐ and out‐degrees that have no good pair. The result settles a conjecture by Thomassen for digraphs of independence number 2. We prove that every digraph on at most 6 vertices and arc‐connectivity at least 2 has a good pair and give an example of a 2‐arc‐strong digraph on 10 vertices with independence number 4 that has no good pair. We also show that there are infinitely many digraphs with independence number 7 and arc‐connectivity 2 that have no good pair. Finally we pose a number of open problems.

Zitieren

APA

Bang‐Jensen, J., Bessy, S., Havet, F., & Yeo, A. (2022). Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2. Journal of Graph Theory, 100(2), 294-314. https://doi.org/10.1002/jgt.22779

Vancouver

Bang‐Jensen J, Bessy S, Havet F, Yeo A. Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2. Journal of Graph Theory. 2022;100(2):294-314. doi:10.1002/jgt.22779

BibTeX
@article{BangJensen2022,
  author = {Bang‐Jensen, Jørgen and Bessy, Stéphane and Havet, Frédéric and Yeo, Anders},
  title = {Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2},
  journal = {Journal of Graph Theory},
  year = {2022},
  volume = {100},
  number = {2},
  pages = {294--314},
  doi = {10.1002/jgt.22779}
}
Kostenlos starten →