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

超图H=(V,E)顶点集为V,边集为E.S(C)V是H的顶点子集,如果HS不含有圈,则称S是H的点反馈数,记tc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则tc(H)≤m/3;(ii)如果日是3-一致超图,边数为m,则Tc(H)≤m/2并且等式成立当且仅当日任何一个连通分支是孤立...

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 HS 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.