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

Decycling Number and Upper-Embeddibility of Generalized Petersen Graphs

作　　者：魏二玲[1] 李益凡[1] 

机构地区：[1]中国人民大学数学系,北京100872

出　　处：《数学学报（中文版）》2013年第2期211-216,共6页Acta Mathematica Sinica：Chinese Series

基　　金：中国人民大学科学研究基金(中央高校基本科研业务费专项资金资助)10xNB054项目成果

摘　　要：给定图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.

关 键 词：广义PETERSEN图 独立集 消圈数 上嵌入 

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