| 几类特殊有向循环图的核 |
| |
| 引用本文： | 任秀秀,杨卫华.几类特殊有向循环图的核[J].数学进展,2019(2):137-144. |
| |
| 作者姓名： | 任秀秀 杨卫华 |
| |
| 作者单位： | 太原理工大学数学学院 |
| |
| 基金项目： | 国家自然科学基金资助课题(Nos.11671296) |
| |
| 摘 要： | 有向图D=(V,A)的核K是顶点集V的一个子集,其中K中任意两点在D中均不相邻,并且对V\K中任意一个点v,都存在K中的一个点u,使得(v,u)是D中的一条弧.一般有向图核的存在问题是NP-完全的.Bang-Jensen和Gutin在他们的著作Digraphs:Theory, Algorithms and Applications, London:Springer-Verlag, 2000]中提出公开问题(Problem 12.3.5):刻画有向循环图核存在性.本文研究了几类特殊有向循环图核的存在问题,并给出了Duchet核猜想(对任意一个不是有向奇圈的无核有向图,都存在一条弧,使得删除这条弧所得到的图仍然是无核的)的一类反例.
|
| 关 键 词： | 核 有向图 循环图 Duchet核猜想 |
The Kernel in Special Directed Circular Graphs |
| |
| REN Xiuxiu,YANG Weihua.The Kernel in Special Directed Circular Graphs[J].Advances in Mathematics,2019(2):137-144. |
| |
| Authors: | REN Xiuxiu YANG Weihua |
| |
| Institution: | (College of Mathematics,Taiyuan University of Technology,Taiyuan,Shanxi,030024,P.R.China) |
| |
| Abstract: | REN Xiuxiu;YANG Weihua(College of Mathematics,Taiyuan University of Technology,Taiyuan,Shanxi,030024,P.R.China) |
| |
| Keywords: | kernel directed graph circular graph Duchet kernel conjecture |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
