Decomposing oriented graphs into transitive tournaments

DOI10.1016/J.DISC.2005.11.008MaRDI QIDQ817766zbMATH OpenOpenAlexFDO

Authors Raphael Yuster

Publication date 20 March 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.11.008

zbMATH Keywords

decomposition

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

If \(G\) is an oriented graph with \(n\) vertices, let \(f(G)\) denote the least number of arc-disjoint transitive subtournaments whose union includes all arcs of \(G\). The author shows that, in general, \(f(G)\leq\lfloor n^2/3\rfloor\) and that equality holds when \(G\) has at most \(n^2/3\) arcs. He also shows, among other things, that if \(G\) is a tournament, then \((n^2/3000)(1+ o(1))< f(G)< (5n^2/21)(1+ o(1))\).

Recommendations

• A note on decompositions of transitive tournaments. II
• A note on decompositions of transitive tournaments
• A note on a packing problem in transitive tournaments
• Packing of three copies of a digraph into the transitive tournament
• Some extremal properties concerning transitivity in graphs

Cites work

• Disproof of a conjecture of Erdös and moser on tournaments
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• Near perfect coverings in graphs and hypergraphs
• The number of edge-disjoint transitive triples in a tournament
• The Representation of a Graph by Set Intersections

Cited in

(6)

• Counting orientations of graphs with no strongly connected tournaments
• Transitive tournaments and self-complementary graphs
• A note on decompositions of transitive tournaments. II
• Transitive tournament tilings in oriented graphs with large minimum total degree
• A note on decompositions of transitive tournaments
• A note on an embedding problem in transitive tournaments

This page was built for publication: Decomposing oriented graphs into transitive tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817766)