×

zbMATH — the first resource for mathematics

Adding and reversing arcs in semicomplete digraphs. (English) Zbl 0892.05019
Suppose \(T\) is a semicomplete digraph on \(n\) vertices. Let \(a\) denote the minimum number of arcs whose addition to \(T\) results in a \(k\)-connected semicomplete digraph, and \(r\) denote the minimum number of arcs whose reversal in \(T\) results in a \(k\)-connected semicomplete digraph. The authors prove that if \(n\geq 3k-1\), then \(a=r\) and that this bound on \(n\) is the best possible.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI