关于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性质

对两个给定的图G和H ,以G +H表示G和H的联 ,以G[H]表示G对图H的结合图 ,证明了如下结果 :(1)G +H是Menger图当且仅当G和H均为Menger图 ;(2 )若G和H均为Menger图 ,且G的任一导出子图也是Menger图 ,则G[H]必为Menger图 .

关于几类Menger型图

设Ｇ是一个简单图．若分离Ｇ的任一独立集Ｓ的最小点数等于连接Ｓ的点之间的内部不相交路的最大个数，则称Ｇ是Ｍｅｎｇｅｒ型图．本文讨论了几类Ｍｅｎｇｅｒ型图．

关于menger定理的推广的注

本文给出了一个图为Ｍｅｎｇｅｒ型的一个充分必要条件、利用这个条件下，我们拓广了已知的Ｍｅｎｇｅｒ型图的类．