Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T09:15:44.896Z Has data issue: false hasContentIssue false
  • English
  • Français

Adding and Reversing Arcs in Semicomplete Digraphs

Published online by Cambridge University Press:  01 March 1998

JØRGEN BANG-JENSEN  and
TIBOR JORDÁN
JØRGEN BANG-JENSEN
Affiliation:
Department of Mathematics and Computer Science, Odense University, Campusvej 55 DK-5230 Odense, Denmark (e-mail: jbj@imada.ou.dk and tibor@imada.ou.dk)
TIBOR JORDÁN
Affiliation:
Department of Mathematics and Computer Science, Odense University, Campusvej 55 DK-5230 Odense, Denmark (e-mail: jbj@imada.ou.dk and tibor@imada.ou.dk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 7 , Issue 1 , March 1998 , pp. 17 - 25
Copyright
1998 Cambridge University Press