Packing triangles in weighted graphs

Details Packing triangles in weighted graphs Packing triangles in weighted graphs

2010-12-02

arxiv.org/abs/1012.0372v1

Mathematics

Combinatorics

Scientific paper

Tuza conjectured that for every graph G, the maximum size {\nu} of a set of edge-disjoint triangles and minimum size {\tau} of a set of edges meeting all triangles, satisfy {\tau} at most 2{\nu}. We consider an edge-weighted version of this conjecture, which amounts to packing and covering triangles in multigraphs. Several known results about the original problem are shown to be true in this context, and some are improved. In particular, we answer a question of Krivelevich who proved that {\tau} is at most 2{\nu}* (where {\nu}* is the fractional version of {\nu}), and asked if this is tight. We prove that {\tau} is at most 2{\nu}*-sqrt({\nu}*)/4 and show that this bound is essentially best possible.

Affiliated with

Also associated with

No associations

Rating

Packing triangles in weighted graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Packing triangles in weighted graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packing triangles in weighted graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-603262