极小k边连通有向图中出度为k的点

摘要：

设k是正整数,D是极小k边连通简单有向图.Mader猜测(见Combinatorics,Paul Erdos is Eighty(Vol.2),Budapest,1996)D中至少有k+1个出度为k的点.在k=1时,Mader已证明成立.考虑k≥2,运用Edmonds等人在研究组合优化问题中引入的对无交叉组的树表示,证明了在k≥2时,D中至少有3个出度为k的点.

关键词：图论、极小k边连通有向图、组合优化、无交叉组、树表示

所属期刊栏目：22

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金10171022;广西科学基金0135028

在线出版日期：2004-08-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：25-31