关于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-困难的.