Packing and covering directed triangles

DOI10.1007/S00373-020-02167-8MaRDI QIDQ2191263zbMATH OpenOpenAlexFDO

Authors Jessica McDonald, Gregory J. Puleo, Craig Tennenhouse

Publication date 24 June 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

digraphscoveringpackingtriangles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that if a directed multigraph $D$ has at most $t$ pairwise arc-disjoint directed triangles, then there exists a set of less than $2t$ arcs in $D$ which meets all directed triangles in $D$, except in the trivial case $t=0$. This answers affirmatively a question of Tuza from 1990.

Recommendations

• Packing and covering directed triangles asymptotically
• Packing and covering triangles in planar graphs
• Packing triangles in regular tournaments
• Directed triangles in directed graphs
• On a conjecture of Tuza about packing and covering of triangles

Cites work

• A conjecture on triangles of graphs
• Dense graphs with a large triangle cover have a large triangle packing
• Integer and fractional packings in dense graphs
• On a conjecture of Tuza about packing and covering of triangles
• Packing and covering triangles in \(K_{4}\)-free planar graphs
• Packing and covering triangles in graphs
• Packing triangles in weighted graphs
• Perfect Triangle Families
• Small edge sets meeting all triangles of a graph
• Tuza's conjecture for graphs with maximum average degree less than 7
• Tuza's conjecture is asymptotically tight for dense graphs

Cited in

(9)

• Directed triangles in directed graphs
• Packing arc-disjoint cycles in oriented graphs
• Packing triangles in regular tournaments
• Packing and covering triangles in planar graphs
• Packing and Covering a Given Directed Graph in a Directed Graph
• Packing and covering triangles in graphs
• scientific article; zbMATH DE number 3861185 (Why is no real title available?)
• Packing and covering directed triangles asymptotically
• scientific article; zbMATH DE number 1275586 (Why is no real title available?)

This page was built for publication: Packing and covering directed triangles

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