Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles
Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles
复制标题
DOI：
10.1007/978-3-319-44543-4_21
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Xujin Chen;Zhuo Diao;Xiaodong Hu;Zhongzheng Tang
中科院分区：
文献类型：
--
作者：
Xujin Chen;Zhuo Diao;Xiaodong Hu;Zhongzheng Tang
给定一个简单的图，如果它与g的每个三角形相交，则称为三角形覆盖。让我们分别表示成对边不相交三角形的最大数目和三角形覆盖g的最小基数。图扎在1981年推测，每一个图形都成立。本文采用超图方法，设计了一种多项式时间组合算法，用于寻找小三角形覆盖。这些算法为图扎关于覆盖和填充三角形的猜想提供了新的充分条件。更准确地说，假设三角形集合覆盖了所有的边。我们证明，如果满足下列条件之一，则可以在多项式时间内找到最多具有基数的g的三角形覆盖：(i), (ii), （iii）。
Given a simple graph, a subset ofEis called a triangle cover if it intersects each triangle ofG. Letanddenote the maximum number of pairwise edge-disjoint triangles inGand the minimum cardinality of a triangle cover ofG, respectively. Tuza conjectured in 1981 thatholds for every graphG. In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding small triangle covers. These algorithms imply new sufficient conditions for Tuza’s conjecture on covering and packing triangles. More precisely, suppose that the setof triangles covers all edges inG. We show that a triangle cover ofGwith cardinality at mostcan be found in polynomial time if one of the following conditions is satisfied: (i), (ii), (iii).