关键词: Menger集, Menger图, Menger数, NP

Abstract:

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.

Key words: Menger’s set, Menger’s graph, Menger’s number, NP hard.