Abstract
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.
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Journal of Graph Theory |
| Vol/bind | 103 |
| Udgave nummer | 1 |
| Sider (fra-til) | 5-11 |
| ISSN | 0364-9024 |
| DOI | |
| Status | Udgivet - 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.