Packing and Covering a Given Directed Graph in a Directed Graph

DOI10.1137/22M1534134MaRDI QIDQ6146269zbMATH OpenOpenAlexFDO

Authors Raphael Yuster

Publication date 10 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2312.01901

zbMATH Keywords

approximationcoveringcyclepacking

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Packing directed cycles efficiently
• Mathematical Foundations of Computer Science 2004
• Packing directed circuits through prescribed vertices bounded fractionally
• Packings and coverings of the complete directed multigraph with 3- and 4-circuits
• Packing directed circuits fractionally

Cites work

• A conjecture on triangles of graphs
• An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
• Approximating maximum subgraphs without short cycles
• Constructive Quasi-Ramsey Numbers and Tournament Ranking
• Dense graphs with a large triangle cover have a large triangle packing
• scientific article; zbMATH DE number 3333210 (Why is no real title available?)
• Integer and fractional packing of families of graphs
• Integer and fractional packings in dense graphs
• Node-and edge-deletion NP-complete problems
• On a conjecture of Tuza about packing and covering of triangles
• On pancyclic digraphs
• Packing and covering directed triangles
• Packing and covering directed triangles asymptotically
• Packing and covering triangles in graphs
• Packing directed cycles efficiently
• Testing subgraphs in directed graphs
• The probabilistic method
• Tuza's conjecture is asymptotically tight for dense graphs

This page was built for publication: Packing and Covering a Given Directed Graph in a Directed Graph

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