消圈数与图的嵌入（英文）

Decycling Number and Graph Embeddings

设▽(G)表示最少的点数,这些点去掉后图中无圈(即森林).称这个数▽(G)为图G的消圈数.通常,确定图的消圈数是NP完全的.Bau和Beineke曾提出以下问题:哪些阶数为n的3正则图G的消圈数满足▽(G)=[(n+2)/4]?本文回答了这个问题:阶数为n的3正则图G的消圈数满足▽(G)=[(n+2)/4]当且仅当G是上嵌入的(即以最多两个面嵌入在可定向曲面上).其次,对于一般3正则图,得出其消圈数的计算公式为▽(G)=γ_M(G)+ζ(G),这里γ_M(G)表示图的最大亏格,ζ(G)表示图G的Betti亏数.由此可知,3正则图的最大亏格的计算的多项式算法是存在的,所以3正则图的消圈数的计算也是多项式可解的.

Let ▽（G） denote the minimum number of vertices whose removal results in an acyclic graph（i.e.,a forest）.Such a number ▽（G） is called the decycling number of graph G.In general,deciding the decycling number of a graph is NP-complete.Bau and Beineke proposed the following question：Which cubic graphs G of order n satisfy ▽（G） =[（n＋2）/4]？ In this paper we solve this problem and show that a cubic graph G of order n has decycling number▽（G） =[（n＋2）/4]if and only if G is upper-embeddable（i.e.,may be embedded in an orientable surface having at most two faces）.Furthermore,we find that the decycling number of a cubic graph G is ▽（G） = γ_m（G） ＋ ζ（G）,where γ_m（G） and ζ（G） are,respectively,the maximum genus of G and the Betti deficiency of G.Since there exists a polynomial time algorithm to find the maximum genus of cubic a graph,there also exists a polynomial time algorithm to find the decycling number of a cubic graph.