文献类型：期刊文章

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

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

出　　处：《数学学报（中文版）》

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

年　　份：2013

卷　　号：56

期　　号：2

起止页码：211-216

语　　种：中文

收录情况：BDHX、BDHX2011、CSCD、CSCD2013_2014、IC、INSPEC、JST、MR、RCCSE、SCIE、SCOPUS、ZGKJHX、ZMATH、核心刊

摘　　要：给定图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].利用消圈集的性质,进一步可推出,这类图是上可嵌入的.

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

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