A003141 - OEIS

This site is supported by donations to The OEIS Foundation.

A003141

Minimal number of arcs whose reversal yields a transitive tournament.
(Formerly M2334)

0, 0, 0, 1, 1, 3, 4, 7, 8, 12, 15, 20 (list; graph; refs; listen; history; 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	J.-C. Bermond, Ordres a` distance minimum d'un tournoi et graphs partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25. `Don Coppersmith, Lisa Fleischer and Atri Rudra: Ordering by weighted number of wins gives a good ranking for weighted tournaments. SODA 2006: 776-782.` `K. B. Reid, On sets of arcs containing no cycles in tournaments, Canad. Math. Bull., 12 (1969), 261-264.` `Sanchez-Flores, Neumann-Lara and Bermond, Graphs & Combin 10 (1994) 363-366 and 367-376.` `Sanchez-Flores, Neumann-Lara and Bermond, Math. Sci. Humaines 37 (1972) 5-25.` `N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).`
	LINKS	`W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs [Has much more information]` `Yahoo Groups, Range Voting` `Index entries for sequences related to tournaments`
	FORMULA	`The asymptotics for large n are (n+1)n/4-Cn^{3/2} <= F(n) <= (n+1)n/4-Kn^{3/2} for all sufficiently large n and certain constants C,K>0. - Warren Smith, Sep 14 2006`
	CROSSREFS	`Equals C(n, 2) - A001225.` `Sequence in context: A165157 A129819 A025032 * A157419 A008368 A023054` `Adjacent sequences: A003138 A003139 A003140 * A003142 A003143 A003144`
	KEYWORD	`hard,nonn,nice`
	AUTHOR	`N. J. A. Sloane (njas(AT)research.att.com).`
	EXTENSIONS	`Additional comments from Warren D. Smith, Sep 14 2006`

Content is available under The OEIS End-User License Agreement .

Last modified February 14 07:57 EST 2012. Contains 205603 sequences.