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

超图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.

On the Feedback Number of 3-uniform Hypergraphs

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.