3-一致超图的反馈数研究  

On the Feedback Number of 3-uniform Hypergraphs

作　　者：刁卓 DIAO Zhuo(School of Statistics and Mathematics,Central University of Finance and Economics,Beijing,100081,P.R.China)

机构地区：[1]中央财经大学统计与数学学院,北京100081

出　　处：《数学进展》2020年第1期13-19,共7页Advances in Mathematics（China）

基　　金：Supported by NSFC(No.11901605).

摘　　要：超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τc(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τc(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τc′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τc’(H)≤2m-n+p.Let H=(V,E) be a hypergraph with vertex set V and edge set E.S■V is a feedback vertex set(FVS) of H if H\S has no cycle and τ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 τc(H)≤m/3;(ii) if H is a 3-uniform hypergraph with m edges,then τc(H)≤and furthermore,the equality holds if and only if every component of H is an isolated vertex or a2-cycle.A■E is a feedback edge set(FES) of H if H \ A has no cycle and τ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 τc′(H)≤2 m-n+p.

关 键 词：点反馈数 边反馈数 3-一致超图 

分 类 号：O157.5[理学—数学]