簡易檢索 / 詳目顯示
| 研究生： |
呂昀珊 Lu, Yun-Shan |
|---|---|
| 論文名稱： |
Tuza 常數之研究 A study on the Tuza constants |
| 指導教授： |
王弘倫
Wang, Hung-Lung |
| 口試委員： |
韓永楷
Hon, Wing-Kai 紀博文 Chi, Po-Wen 王弘倫 Wang, Hung-Lung |
| 口試日期： | 2022/08/02 |
| 學位類別： |
碩士 Master |
| 系所名稱： |
資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年： | 2022 |
| 畢業學年度： | 110 |
| 語文別： | 英文 |
| 論文頁數： | 41 |
| 中文關鍵詞： | 橫截 、k-均勻超圖 、Tuza 常數 |
| 英文關鍵詞： | Transversal, k-uniform hypergraph, Tuza constants |
| 研究方法: | 紮根理論法 、 主題分析 、 比較研究 |
| DOI URL： | http://doi.org/10.6345/NTNU202201674 |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：16 下載：8 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
令 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.
[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.
