| 关于Menger图和Menger数的若干结果 |
| |
| 引用本文： | 原晋江.关于Menger图和Menger数的若干结果[J].数学物理学报(A辑),2005,25(1):93-97. |
| |
| 作者姓名： | 原晋江 |
| |
| 作者单位： | 郑州大学数学系 郑州450052 |
| |
| 基金项目： | 国家自然科学基金(10371112)，河南省自然科学基金(0411011200)资助 |
| |
| 摘 要： | 该文研究Menger图和Menger数. 主要结果如下 :
(1)\ 对任意的n≥4, n立方体Q\-n不是Menger图. 解决了Sampathkumar提出的未解问题2.
(2)\ 如果G是一个偶图, 则m(G)=β\-0(G),其中m(G)是G的Menger数, β\-0(G)是G的独立数. 部分解决了Sampathkumar提出的未解问题3.
(3)\ “确定图的Menger数”问题是NP困难的.
|
| 关 键 词： | Menger集 Menger图 Menger数 NP |
| 文章编号： | 1003-3998(2005)01-093-05 |
| 修稿时间： | 2002年12月12 |
Some Results about Menger's Graph and Menger's Number |
| |
| YUAN Jin-Jiang.Some Results about Menger''''s Graph and Menger''''s Number[J].Acta Mathematica Scientia,2005,25(1):93-97. |
| |
| Authors: | YUAN Jin-Jiang |
| |
| 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. |
| |
| Keywords: | Menger&rsquo s setzz Menger&rsquo s graphzz Menger&rsquo s numberzz NP hard zz |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《数学物理学报(A辑)》浏览原始摘要信息 |
| 点击此处可从《数学物理学报(A辑)》下载免费的PDF全文 |
