Tuza 常數之研究

Abstract

令 H 為一點集合為 V (H) 和邊集合為 E(H) 的超圖。橫截 (transversal) 是超圖 H 中一組點的集合，使得 H 中的每條邊都會與該集合至少交於一點。橫截數 (transversal number) τ (H) 是 H 中最小橫截的大小。如果 H 的每一條邊大小都是 k，我們會稱 H 是 k-均勻 ( k-uniform) 超圖並且會以 H_k 來表示。Tuza 常數 c_k 是一個滿足 τ (H_k) ≤ c_k(|V (H_k)| + |E(Hk)|) 的常數。目前 Tuza 常數 c_k 在 k ≥ 5 的精確值皆未知。Henning 和 Yeo 證明了 c6 ≤ 2569/14145，延伸他們的想法我們建立了當 7 ≤ k ≤ 17 時 c_k 的上界。此外，我們也建立當 7 ≤ k ≤ 17 時 c_k 的下界。

Let H be a hypergraph with vertex set V (H) and edge set E(H). A transversal is a subset of V (H) such that every edge in H intersects this set. The cardinality of a minimum transversal of H is denoted by τ (H). A hypergraph in which every edge has size k is called a k-uniform hypergraph. The Tuza constants c_k are the constants satisfying τ (H) ≤ c_k(|V (H)|+|E(H)|), where H ranges over all k-uniform hypergraphs. The precise value of c_k for k ≥ 5 is currently unknown. Henning and Yeo showed that c_6 ≤ 2569/14145 . Extending their idea, we establish upper bounds on c_k, for 7 ≤ k ≤ 17. We also give lower bounds on c_k, for 7 ≤ k ≤ 17.