 北京大学期刊网　|　作者　　审稿人　　编委专家　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展 - 2020, Vol. 49(1): 13-19
 研究论文
 $3$-一致超图的反馈数研究 On the Feedback Number of $3$-uniform Hypergraphs 刁卓 DIAO Zhuo 中央财经大学统计与数学学院, 北京, 100081 School of Statistics and Mathematics, Central University of Finance and Economics, Beijing, 100081, P. R. China 收稿日期: 2018-11-04 出版日期: 2020-03-25 2020, Vol. 49(1): 13-19 DOI: 10.11845/sxjz.2018095b PDF [184 KB] 42 下载 114 浏览 引用导出
0
/   /   推荐 Abstract：Let $H=(V,E)$ be a hypergraph with vertex set $V$ and edge set $E$. $S\subseteq V$ is a feedback vertex set (FVS) of $H$ if $H\setminus S$ has no cycle and $\tau_c(H)$ denotes the minimum cardinality of an FVS of $H$. In this paper, we prove: (i) if $H$ is a linear $3$-uniform hypergraph with $m$ edges, then $\tau_c(H)\le \frac{m}{3}$; (ii) if $H$ is a $3$-uniform hypergraph with $m$ edges, then $\tau_c(H)\le \frac{m}{2}$ and furthermore, the equality holds if and only if every component of $H$ is an isolated vertex or a $2$-cycle. $A\subseteq E$ is a feedback edge set (FES) of $H$ if $H\setminus A$ has no cycle and $\tau_c'(H)$ denotes the minimum cardinality of an FES of $H$. In this paper, we prove if $H$ is a $3$-uniform hypergraph with $p$ components, then $\tau_c'(H)\le 2m-n+p$.
Key wordsfeedback vertex set    feedback edge set    $3$-uniform hypergraphs
 PACS: O157.5

  Alon, N. and Spencer, J.H., The Probabilistic Method, 4th Edition, New York: John Wiley & Sons, 2016. Bafna V., Berman P. and Fujito T., A 2-approximation algorithm for the undirected feedback vertex set problem, SIAM J. Discrete Math., 1999, 12(3): 289-297. Berge C.,Hypergraphs, North-Holland Mathematical Library, Vol. 45, Amsterdam: North-Holland Publishing Co., 1989. Brualdi R.A.,Introductory Combinatorics, 5th Edition, Upper Saddle River, NJ: Pearson Prentice Hall, 2010. Diestel R.,Graph Theory, 3rd Edition, Grad. Texts in Math., Vol. 173, Berlin: Springer-Verlag, 2005. Erdős, P. and Pósa, L., On independent circuits contained in a graph, Canadian J. Math., 1965, 17: 347-352. Festa, P., Pardalos, P.M. and Resende, M.G.C., Feedback set problems, In: Handbook of Combinatorial Optimization, Supplement Vol. A, Dordrecht: Kluwer Acad. Publ., 1999, 209-258. Fomin F.V., Gaspers S., Pyatkin A.V. and Razgon I., On the minimum feedback vertex set problem: exact and enumeration algorithms, Algorithmica, 2008, 52(2): 293-307.
  黄丹君, 王阳. Halin图的线性$k$-点荫度[J]. 数学进展, 2020, 49(4): 401-405.  段秀转, 王健, 杨卫华. 关于线性森林的广义图兰问题研究[J]. 数学进展, 2020, 49(4): 406-412.  王艳, 周金秋. 3-边可染的3-正则图[J]. 数学进展, 2020, 49(4): 413-417.  王一鑫. 海森堡群上BMO型空间的Carleson测度刻画[J]. 数学进展, 2020, 49(3): 305-312.  赵良, 吴藏. 具有对合的自反环[J]. 数学进展, 2020, 49(3): 299-304.  关夏夏, 吴楚雄, 杨卫华, 孟吉翔. 平面图书式嵌入综述[J]. 数学进展, 2020, 49(1): 1-12.  于桂海, 侯耀平, 曲慧. 完全图的单钩immanant[J]. 数学进展, 2019, 48(6): 692-698.  覃荣存, 赵恒明. 通过半循环可分组设计构造变重量光正交码[J]. 数学进展, 2019, 48(6): 699-711.  卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155.  任秀秀,杨卫华. 几类特殊有向循环图的核[J]. 数学进展, 2019, 48(2): 137-144.  石慧苓, 高云澍. 标准多重图中点不交的重边四边形[J]. 数学进展, 2018, 47(3): 348-362.  卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372.  邓兴超, 宋贺, 苏贵福, 田润丽. 小直径二连通外平面图的彩虹连通数[J]. 数学进展, 2018, 47(3): 373-382.  田方. 一类稀疏随机图的距离匹配数[J]. 数学进展, 2018, 47(2): 175-188.  朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681.
Viewed
Full text

Abstract

Cited

Discussed