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

Some Results about Menger’s Graph and Menger's Number

该文研究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.