Packing of two digraphs into a transitive tournament

DOI10.1016/J.DISC.2005.11.038MaRDI QIDQ868371zbMATH OpenOpenAlexFDO

Authors Monika Pilśniak

Publication date 2 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

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

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

It can be shown that if the number of arcs in a digraph of order \(n\) without directed cycles is sufficiently small, not greater than \(3(n - 1)/4\), then two copies of this digraph are packable into a transitive tournament. The paper presents a generalization of this result by showing that if the sum of the sizes of two digraphs of order \(n\) without directed cycles is not greater than \(3(n - 1)/2\), then these two digraphs are packable into a transitive tournament.

Recommendations

• Packing of three copies of a digraph into the transitive tournament
• A note on a packing problem in transitive tournaments
• scientific article; zbMATH DE number 3968612
• On packable digraphs
• Packing transitive triples in a tournament

Cites work

• Edge disjoint placement of graphs
• Every (p,p-2) graph is contained in its complement
• scientific article; zbMATH DE number 3943825 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 1022391 (Why is no real title available?)
• Packing of graphs - a survey
• Packings of graphs and applications to computational complexity

Cited in

(7)

• Packing transitive triples in a tournament
• \(\text{TT}_n\)-maximal digraphs of the minimum size
• A note on a packing problem in transitive tournaments
• scientific article; zbMATH DE number 3968612 (Why is no real title available?)
• Packing of three copies of a digraph into the transitive tournament
• On packable digraphs
• A note on an embedding problem in transitive tournaments

This page was built for publication: Packing of two digraphs into a transitive tournament

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