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.
| Original language | English |
|---|---|
| Pages (from-to) | 5-11 |
| Number of pages | 7 |
| Journal | Journal of Graph Theory |
| Volume | 103 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - May 2023 |
| Externally published | Yes |
Keywords
- directed vertex-connectivity augmentation
- increasing connectivity
- one-way pairs
- semicomplete digraph
- tournament
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics