多叶生成树及N.Linial猜想
来源期刊：东北大学学报(自然科学版)1992年第5期
论文作者：郝培锋
文章页码：518 - 520
关键词：最小支配集;生成树;顶点数;叶数;r-正则图;
摘 要：利用简单图G 的最小支配集顶点数γ刻画了该图的最多叶生成树中叶数的下确界。即 L（G）≥n-3γ+2。其中 L（G）表示图 G的生成树的叶数,n是G 的顶点数。同时对于 N.Linial 关于r-正则留图的最多叶生成树叶数的猜想公式 L（G）≥n·（（r-2）/（r+1））+d 中的 d做出了估计,即 d≤（r+4）/（r+1） r=2k d≤（r+7）/（r+1） r=2k+1
郝培锋
东北工学院数学系
摘 要：利用简单图G 的最小支配集顶点数γ刻画了该图的最多叶生成树中叶数的下确界。即 L（G）≥n-3γ+2。其中 L（G）表示图 G的生成树的叶数,n是G 的顶点数。同时对于 N.Linial 关于r-正则留图的最多叶生成树叶数的猜想公式 L（G）≥n·（（r-2）/（r+1））+d 中的 d做出了估计,即 d≤（r+4）/（r+1） r=2k d≤（r+7）/（r+1） r=2k+1
关键词：最小支配集;生成树;顶点数;叶数;r-正则图;
