|
|
A003141
|
|
Minimal number of arcs whose reversal yields a transitive tournament.
(Formerly M2334)
|
|
5
|
|
|
0, 0, 0, 1, 1, 3, 4, 7, 8, 12, 15, 20, 22, 28
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
This is the "minimum feedback arc set" problem.
The minimal number of arcs you need to delete to make a directed graph acyclic (maxed over all n-vertex directed graphs) is the same as the minimal number of arcs you need to reverse to make a tournament acyclic (maxed over all n-player tournaments).
|
|
REFERENCES
|
Sanchez-Flores, Neumann-Lara and Bermond, Graphs & Combin 10 (1994) 363-366 and 367-376.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
The asymptotics for large n are (n+1)*n/4 - C*n^(3/2) <= F(n) <= (n+1)*n/4 - K*n^(3/2) for all sufficiently large n and certain constants C, K > 0. - Warren D. Smith, Sep 14 2006
|
|
CROSSREFS
|
|
|
KEYWORD
|
hard,more,nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Irène Charon and Olivier Hudry
|
|
STATUS
|
approved
|
|
|
|