Making a tournament k-strong

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

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

47 Downloads (Pure)

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.

OriginalsprogEngelsk
TidsskriftJournal of Graph Theory
Vol/bind103
Udgave nummer1
Sider (fra-til)5-11
ISSN0364-9024
DOI
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.

Fingeraftryk

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

Citationsformater