摘要
该文研究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-困难的.
This paper discusses the Menger’s graph and Menger’s number. The main results are as follows (1) For any n≥4, the n-cube Q-n is not a Menger’s graph. This answers the open problem 2 posed by Sampathkumar. (2) If G is a bipartite graph, then m(G)=β-0(G), where m(G) is the Menger’s number of G and β-0(G) is the independent number of G. This partially answers the open problem 3 posed by Sampathkumar. (3) The problem “determining the Menger’s number of a graph” is NP-hard.
出处
《数学物理学报（A辑）》
CSCD
北大核心
2005年第1期93-97,共5页
Acta Mathematica Scientia
基金
国家自然科学基金(10371112)
河南省自然科学基金(0411011200)资助
