运筹学

5-一致超图的全横贯

展开
  • 1. 上海大学数学系, 上海 200444;  2. 上海大学管理学院, 上海 200444; 

收稿日期: 2015-11-13

  网络出版日期: 2016-06-15

基金资助

国家自然科学基金(No. 11571222)

Total transversals in 5-uniform hypergraphs

Expand
  • 1. Department of Mathematics, Shanghai University,  Shanghai 200444,  China; 2. School of Management,   Shanghai University,  Shanghai 200444,  China

Received date: 2015-11-13

  Online published: 2016-06-15

摘要

设H=(V,E)是以V为顶点集, E为(超)边集的超图. 如果H的每条边均含有k个顶点, 则称H是k-一致超图. 超图H的点子集T称为它的一个横贯, 如果T 与H 的每条边均相交. 超图H的全横贯是指它的一个横贯T, 并且T还满足如下性质: T中每个顶点均至少有一个邻点在T中. H 的全横贯数定义为H 的最小全横贯所含顶点的数目, 记作\tau_{t}(H). 对于整数k\geq 2, 令b_{k}=\sup_{H\in{\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, 其中n_H=|V|, m_H=|E|, {\mathscr{H}}_{k} 表示无孤立点和孤立边以及多重边的k-一致超图类. 最近, Bujt\'as和Henning等证明了如下结果: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}; 当k\geq 5 时, 有b_{k}\leq \frac{2}{7}以及b_{6}\leq \frac{1}{4}; 当k\geq 7 时, b_{k}\leq \frac{2}{9}. 证明了对5-一致超图, b_{5}\leq \frac{4}{15}, 从而改进了当k=5 时b_k的上界.

 

本文引用格式

林苡, 倪振羽, 单而芳 . 5-一致超图的全横贯[J]. 运筹学学报, 2016 , 20(2) : 97 -104 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.009

Abstract

Let H=(V,E) be a hypergraph with vertex set V and edge set E. The hypergraph H is k-uniform if every edge of H have size k. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge in H. A total transversal in H is a transversal T in H with the additional property that every vertex in T is adjacent to some other vertex of T. The total transversal number \tau_{t}(H) of H is the minimum cardinality of a total transversal in H. For k\geq 2, let b_{k}=\sup_{H\in {\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, where {\mathscr{H}}_{k} denotes the class of all k-uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. Recently, Bujt\'as and Henning et al. proved following results: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}. For k\geq 5, b_{k}\leq \frac{2}{7}. What's more, b_{6}\leq\frac{1}{4}, and for k\geq 7, b_{k}\leq \frac{2}{9}. In this paper, we show that b_{5}\leq\frac{4}{15} for 5-uniform hypergraphs and this improves the upper bound of b_{5}.

参考文献

[1] Alon N. Transversal numbers of uniform hypergraphs [J]. Graphs and Combinatorics, 1990, 6: 1-4.
[2] Chv{\'a}tal V, McDiarmid C. Small transversals in hypergraphs [J]. Combinatorica, 1992, 12: 19-26.
[3] Bretto A. Hypergraph Theory-An Introduction [M]. New York: Springer, 2013.
[4] Bujt{\'a}s C, Henning M A, Tuza Zs, et al. Total transversals and total domination in uniform hypergraphs [J]. Electronic Journal of Combinatorics, 2014, 21: \#P2. 24.
[5] Henning M A, Yeo A. Total transversals in hypergraphs and their applications [J]. SIAM Journal on Discrete Mathematics, 2015, 29: 309-320.
[6] Henning M A, Yeo A. Total Domination in Graphs [M]. New York: Springer, 2013.
[7] Henning M A. Recent results on total domination in graphs: A survey [J]. Discrete Mathematics, 2009, 309: 32-63.
[8] Acharya B D. Domination in hypergraphs [J]. AKCE International Journal of Graphs and Combinatorics, 2007, 4: 117-126.
[9] Arumugama S,  Jose K, Bujt\'as C, et al. Equality of domination and transversal numbers in hypergraphs [J]. Discrete Applied Mathematics, 2013, 161: 1859-1867.
[10] Bujt\'{a}s C, Henning M A, Tuza Zs. Transversals and domination in uniform hypergraphs [J]. European Journal of Combinatorics  2012, 33: 62-71.
文章导航

/