Packing Triangles in Weighted Graphs
Packing Triangles in Weighted Graphs
复制标题
DOI：
10.1137/100803869
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
G. Chapuy;Matt DeVos;J. McDonald;B. Mohar;Diego Scheide
中科院分区：
文献类型：
--
作者：
G. Chapuy;Matt DeVos;J. McDonald;B. Mohar;Diego Scheide
Tuza猜想，对于每个图G$，一组边不相交的三角形的最大尺寸$\nu$和一组满足所有三角形的边的最小尺寸$\tau$满足$\tau\leq 2\nu$。我们考虑这个猜想的一个边加权版本，它相当于在多图中填充和覆盖三角形。在这种情况下，关于原问题的几个已知结果被证明是正确的，并且一些结果得到了改进。特别地，我们回答了Krivelevich的一个问题，Krivelevich证明了$\tau\leq 2\nu^*$(其中$\nu^*$是$\nu$的分数版本)，并询问这是否紧。我们证明了$\tau\leq 2\nu^*-\frac{1}{\Sqrt{6}}\Sqrt{\nu^*}$，并证明了这个界本质上是最好的。
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 \leq 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 \leq 2\nu^*$ (where $\nu^*$ is the fractional version of $\nu$) and asked whether this is tight. We prove that $\tau \leq 2\nu^*-\frac{1}{\sqrt{6}}\sqrt{\nu^*}$ and show that this bound is essentially best possible.