Adding and reversing arcs in semicomplete digraphs

Jørgen Bang-Jensen, Tibor Jordan

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

Let T be a semicomplete digraph on n vertices. Let ak(T) denote the minimum number of arcs whose addition to T results in a k-connected semicomplete digraph and let rk(T) denote the minimum number of arcs whose reversal in T results in a k-connected semicomplete digraph. We prove that if n[ges ]3k−1, then ak(T)=rk(T). We also show that this bound on n is best possible.
Original languageEnglish
JournalCombinatorics, Probability & Computing
Volume7
Pages (from-to)17-25
Number of pages9
ISSN0963-5483
DOIs
Publication statusPublished - 1998

Fingerprint Dive into the research topics of 'Adding and reversing arcs in semicomplete digraphs'. Together they form a unique fingerprint.

Cite this