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

作者：魏二玲; 李益凡

来源：数学学报(中文版), 2013, (02): 211-216.

• 广义Petersen图
• 独立集
• 消圈数
• 上嵌入 generalized Petersen graph
• independent set
• decycling number
• upperembeddable

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

• 单位
  中国人民大学