Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 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
    /   /   推荐

摘要 超图$H=(V,E)$顶点集为$V$, 边集为$E$. $S\subseteq V$是$H$的顶点子集, 如果$H\setminus S$不含有圈, 则称$S$是$H$的点反馈数, 记$\tau_c(H)$是$H$的最小点反馈数. 本文证明了: (i) 如果$H$是线性$3$-一致超图, 边数为$m$, 则$\tau_c(H)\le \frac{m}{3}$;(ii) 如果$H$是$3$-一致超图, 边数为$m$, 则$\tau_c(H)\le \frac{m}{2}$ 并且等式成立当且仅当$H$任何一个连通分支是孤立顶点或者长度为$2$的圈. $A\subseteq V$是$H$的边子集, 如果$H\setminus A$不含有圈, 则称$A$是$H$的边反馈数, 记$\tau_c'(H)$是$H$的最小边反馈数. 本文证明了如果$H$是含有$p$个连通分支的$3$-一致超图, 则$\tau_c'(H)\le 2m-n+p$.
关键词 点反馈数边反馈数$3$-一致超图    
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  
通讯作者: E-mail: diaozhuo@amss.ac.cn   
[1] Alon, N. and Spencer, J.H., The Probabilistic Method, 4th Edition, New York: John Wiley & Sons, 2016.
[2] 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.
[3] Berge C.,Hypergraphs, North-Holland Mathematical Library, Vol. 45, Amsterdam: North-Holland Publishing Co., 1989.
[4] Brualdi R.A.,Introductory Combinatorics, 5th Edition, Upper Saddle River, NJ: Pearson Prentice Hall, 2010.
[5] Diestel R.,Graph Theory, 3rd Edition, Grad. Texts in Math., Vol. 173, Berlin: Springer-Verlag, 2005.
[6] Erdős, P. and Pósa, L., On independent circuits contained in a graph, Canadian J. Math., 1965, 17: 347-352.
[7] 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.
[8] 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.
[1] 黄丹君, 王阳. Halin图的线性$k$-点荫度[J]. 数学进展, 2020, 49(4): 401-405.
[2] 段秀转, 王健, 杨卫华. 关于线性森林的广义图兰问题研究[J]. 数学进展, 2020, 49(4): 406-412.
[3] 王艳, 周金秋. 3-边可染的3-正则图[J]. 数学进展, 2020, 49(4): 413-417.
[4] 王一鑫. 海森堡群上BMO型空间的Carleson测度刻画[J]. 数学进展, 2020, 49(3): 305-312.
[5] 赵良, 吴藏. 具有对合的自反环[J]. 数学进展, 2020, 49(3): 299-304.
[6] 关夏夏, 吴楚雄, 杨卫华, 孟吉翔. 平面图书式嵌入综述[J]. 数学进展, 2020, 49(1): 1-12.
[7] 于桂海, 侯耀平, 曲慧. 完全图的单钩immanant[J]. 数学进展, 2019, 48(6): 692-698.
[8] 覃荣存, 赵恒明. 通过半循环可分组设计构造变重量光正交码[J]. 数学进展, 2019, 48(6): 699-711.
[9] 卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155.
[10] 任秀秀,杨卫华. 几类特殊有向循环图的核[J]. 数学进展, 2019, 48(2): 137-144.
[11] 石慧苓, 高云澍. 标准多重图中点不交的重边四边形[J]. 数学进展, 2018, 47(3): 348-362.
[12] 卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372.
[13] 邓兴超, 宋贺, 苏贵福, 田润丽. 小直径二连通外平面图的彩虹连通数[J]. 数学进展, 2018, 47(3): 373-382.
[14] 田方. 一类稀疏随机图的距离匹配数[J]. 数学进展, 2018, 47(2): 175-188.
[15] 朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681.
Viewed
Full text


Abstract

Cited

  Discussed   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .