Packing Triangles in Regular Tournaments. Issue 1 (9th August 2012)

• Record Type: Journal Article
• Authors: Yuster, Raphael
• Is Part Of: Journal of graph theory. Volume 74:Issue 1(2013)
• Page Start: 58
• Page End: 66
• Publication Date: 2012-08-09
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21691
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>We prove that a regular tournament with <italic>n</italic> vertices has more than <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7hz9b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21691:jgt21691-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mfrac><mml:msup><mml:mi>n</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mrow><mml:mn>11.5</mml:mn></mml:mrow></mml:mfrac><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mi>o</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> pairwise arc‐disjoint directed triangles. On the other hand, we construct regular tournaments with a feedback arc set of size less than <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7hz77" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21691:jgt21691-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:msup><mml:mi>n</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mn>8</mml:mn></mml:mfrac></mml:math>, so these tournaments do not have <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7hz54" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21691:jgt21691-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:msup><mml:mi>n</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mn>8</mml:mn></mml:mfrac></mml:math> pairwise arc‐disjoint triangles.</p> </abstract>