广义Petersen图的消圈数与上可嵌入性

Decycling Number and Upper-Embeddibility of Generalized Petersen Graphs

给定图G=(V,E),S■V,若G-S(图G中去掉S中的点以及与其关联的所有边)是一个无圈图,则称S是图G的一个消圈集,且称min{|S|}S是图G的消圈集}为图的消圈数,记为▽(G).图的消圈数的求解是NP完全的.Bau和Beineke提出了如下问题:什么样的阶为2n的3正则图G,其消圈数为[(n+1)/2]?本文对广义Petersen图的消圈数进行了讨论,从而证明了这类图的消圈数恰好为[(n+1)/2].利用消圈集的性质,进一步可推出,这类图是上可嵌入的.

Given a graph G = （V, E）, S V, the minimal number of S whose removal eliminates all the cycles in G is called the decycling number, denoted as ▽（G）. The problem of deternimating the decycling number of a graph is NP-complete. Bau and Beineke proposed the following question： which cubic graphs of order 2n have decycling number [（n＋1）/2]？ In this paper we proved that generalized Petersen graph P（n, k） is such a class of graphs. Based on this result, we proved that P（n, k） is upper-embeddable which generalized a result of Ren.