Tuza 常數之研究

A study on the Tuza constants

呂昀珊(Lu Yun-Shan)

指導教授 ： 王弘倫

國立臺灣師範大學/理學院/資訊工程學系/碩士(2022年)

https://doi.org/10.6345/NTNU202201674

摘要

令 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 的下界。

關鍵字

橫截 ； k-均勻超圖 ； Tuza 常數

並列摘要

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.

並列關鍵字

Transversal ； k-uniform hypergraph ； Tuza constants

參考文獻

[1] M. Aigner and T. Andreae. Vertex-sets that meet all maximal cliques of a graph. manuscript, 1986.

[2] N. Alon. Transversal numbers of uniform hypergraphs. Graphs and Combinatorics, 6:1–4, 1990.

[3] C. Berge. Graphs and Hypergraphs. Amsterdam: North-Holland, 1973.

[4] V. Chvátal and C. McDiarmid. Small transversals in hypergraphs. Combinatorica, 12:19–26, 1992.

[5] M. Dorfling and M. A. Henning. Transversals in 5-uniform hypergraphs and total domination in graphs with minimum degree five. Quaestiones Mathematicae, 38(2):155–180, 2015.