We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Making a tournament k‐strong.
- Authors
Bang‐Jensen, Jørgen; Johansen, Kasper S.; Yeo, Anders
- Abstract
A digraph is k‐strong if it has n k ≥ + 1 vertices and every induced subdigraph on at least n k − + 1 vertices is strongly connected. A tournament is a digraph with no pair of nonadjacent vertices. We prove that every tournament on n k ≥ + 1 vertices can be made k‐strong by adding no more than ( k + 1 2 ) arcs. This solves a conjecture from 1994. A digraph is semicomplete if there is at least one arc between any pair of distinct vertices x, y. Since every semicomplete digraph contains a spanning tournament, the result above also holds for semicomplete digraphs. Our result also implies that for every k ≥ 2, every semicomplete digraph on at least 3k − 1 vertices can be made k‐ strong by reversing no more than ( k + 1 2 ) arcs.
- Subjects
TOURNAMENTS; LOGICAL prediction
- Publication
Journal of Graph Theory, 2023, Vol 103, Issue 1, p5
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22900