Making a tournament k-strong

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

doi:10.1002/jgt.22900

Making a tournament k-strong

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

University of Southern Denmark
Technical University of Denmark

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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	https://doi.org/10.1002/jgt.22900
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

Access to Document

10.1002/jgt.22900

Cite this

@article{10f7151e513c4e31a11fc23e9e5ed6cc,

title = "Making a tournament k-strong",

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.",

keywords = "directed vertex-connectivity augmentation, increasing connectivity, one-way pairs, semicomplete digraph, tournament",

author = "J{\o}rgen Bang-Jensen and Johansen, \{Kasper S.\} and Anders Yeo",

note = "Publisher Copyright: {\textcopyright} 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.",

year = "2023",

month = may,

doi = "10.1002/jgt.22900",

language = "English",

volume = "103",

pages = "5--11",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Making a tournament k-strong

AU - Bang-Jensen, Jørgen

AU - Johansen, Kasper S.

AU - Yeo, Anders

PY - 2023/5

Y1 - 2023/5

N2 - 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.

AB - 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.

KW - directed vertex-connectivity augmentation

KW - increasing connectivity

KW - one-way pairs

KW - semicomplete digraph

KW - tournament

UR - https://www.scopus.com/pages/publications/85139263997

U2 - 10.1002/jgt.22900

DO - 10.1002/jgt.22900

M3 - Article

AN - SCOPUS:85139263997

SN - 0364-9024

VL - 103

SP - 5

EP - 11

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Making a tournament k-strong

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this