Making a tournament k-strong

Jørgen Bang-Jensen*, Kasper S. Johansen, Anders Yeo


Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

47 Downloads (Pure)


A digraph is (Formula presented.) -strong if it has (Formula presented.) vertices and every induced subdigraph on at least (Formula presented.) vertices is strongly connected. A tournament is a digraph with no pair of nonadjacent vertices. We prove that every tournament on (Formula presented.) vertices can be made (Formula presented.) -strong by adding no more than (Formula presented.) arcs. This solves a conjecture from 1994. A digraph is semicomplete if there is at least one arc between any pair of distinct vertices (Formula presented.). Since every semicomplete digraph contains a spanning tournament, the result above also holds for semicomplete digraphs. Our result also implies that for every (Formula presented.), every semicomplete digraph on at least (Formula presented.) vertices can be made (Formula presented.) -strong by reversing no more than (Formula presented.) arcs.

TidsskriftJournal of Graph Theory
Udgave nummer1
Sider (fra-til)5-11
StatusUdgivet - maj 2023

Bibliografisk note

Funding Information:
This research is supported by the Independent Research Fond Denmark under grant number DFF 7014‐00037B.

Publisher Copyright:
© 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.


Dyk ned i forskningsemnerne om 'Making a tournament k-strong'. Sammen danner de et unikt fingeraftryk.