臺灣博碩士論文加值系統

令 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.

Chapter 1 Introduction 1
1.1 Background 2
1.2 Tuza constants 3
1.3 Applications on this topic 6
1.4 The structure of the thesis 8

Chapter 2 Related work 9
2.1 Terminology and Notation 9
2.2 The known results of Tuza constants 10
2.2.1 The precise value of ck 10
2.2.2 An upper bound on c6 11
2.2.3 An lower bound on c5 12
2.3 Two general bounds on ck 13
2.3.1 A general upper bound on ck 13
2.3.2 A general lower bound on ck 14

Chapter 3 Bounds on ck 15
3.1 Upper bounds on ck 15
3.1.1 Establish an upper bound on c7 15
3.1.2 A method of establishing upper bounds 23
3.2 Lower bounds on ck 26

Chapter 4 Further improvement 29
4.1 A further improvement of our results 29
4.2 Comparison of the bounds 35

Chapter 5 Future work 37

References 41

[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.

[6] D.-Z. Du and P.-J. Wan. Connected dominating set: theory and applications. Springer, 2012.

[7] P. Erdős and Z. Tuza. Vertex coverings of the edge set in a connected graph. Graph Theory, Combinatorics, and Applications, Wiley, pages 1179–1187, 1995.

[8] M. A. Henning, C. Löwenstein, J. Southey, and A. Yeo. A new lower bound on the independence number of a graph and applications. Electronic Journal of Combinatorics, 21:1–38, 2014.

[9] M. A. Henning and A. Yeo. Transversals in linear uniform hypergraphs. Developments in Mathematics, Switzerland, 2020.

[10] M. A. Henning and A. Yeo. Lower bounds on tuza constants for transversals in linear uniform hypergraphs. Discrete Applied Mathematics, 304:12–22, 2021.

[11] M. A. Henning and A. Yeo. A new upper bound on the total domination number in graphs with minimum degree six. Discrete Applied Mathematics, 302:1–7, 2021

[12] F.-C. Lai and G. J. Chang. An upper bound for the transversal numbers of 4-uniform hypergraphs. Journal of Combinatorial Theory Series, B, 50:129–133, 1990.

[13] A. Sasireka and A. H. N. Kishor. Applications of dominating set of graph in computer networks. International Journal of Engineering Sciences, 3(1):170–173, 2014.

[14] S. Thomassé and A. Yeo. Total domination of graphs and small transversals of hypergraphs. Combinatorica, 27:473–487, 2007.

[15] Z. Tuza. Covering all cliques of a graph. Discrete Mathematics, 86:117–126, 1990.