login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=0..13.

J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25.

J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25. [Annotated scanned copy]

I. Charon and O. Hudry, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Ann. Oper. Res. 175 (2010), 107-158

Don Coppersmith, Lisa Fleischer and Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, SODA 2006: 776-782.

Robert A. Laird, Brandon S. Schamp, Calculating Competitive Intransitivity: Computational Challenges, The American Naturalist (2018), Vol. 191, No. 4, 547-552.

Range Voting Yahoo Group, Range Voting.

Range Voting Yahoo Group, Introduction. [Cached copy]

RangeVoting.org, Group Website.

K. B. Reid, On sets of arcs containing no cycles in tournaments, Canad. Math. Bull., 12 (1969), 261-264.

W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs [Has much more information]

Index entries for sequences related to tournaments

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

Equals C(n, 2) - A001225.

a(n) = A182079(n) iff n <= 9, thereafter a(n) > A182079(n). [Bermond]

Sequence in context: A129819 A025032 A207524 * A284491 A284506 A157419

Adjacent sequences:  A003138 A003139 A003140 * A003142 A003143 A003144

KEYWORD

hard,more,nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Irène Charon and Olivier Hudry.

Terms a(12) and a(13) from Christian Stricker, Jan 14 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 09:09 EDT 2020. Contains 337380 sequences. (Running on oeis4.)