关于Menger图和Menger数的若干结果

摘要：

该文研究Menger图和Menger数. 主要结果如下(1)对任意的n≥4, n立方体Qn不是Menger图. 解决了Sampathkumar提出的未解问题2.(2)如果G是一个偶图, 则m(G)=β0(G),其中m(G)是G的Menger数, β0(G)是G的独立数. 部分解决了Sampathkumar提出的未解问题3.(3)"确定图的Menger数"问题是NP-困难的.

关键词：Menger集、Menger图、Menger数、NP-困难

所属期刊栏目：25

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金10371112;河南省自然科学基金0411011200

在线出版日期：2005-03-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：93-97