| k-连通图中生成树和完美匹配上的可收缩边 |
| |
| 引用本文： | 王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报(理学版), 2016, 51(8): 29-34. DOI: 10.6040/j.issn.1671-9352.0.2016.148 |
| |
| 作者姓名： | 王倩 |
| |
| 作者单位： | 山东大学数学学院, 山东 济南 250100 |
| |
| 基金项目： | 国家自然科学基金资助项目(61432010) |
| |
| 摘 要： | 给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2+1条可收缩边。
|
| 关 键 词： | k-连通图 可收缩边 生成树 完美匹配 |
| 收稿时间： | 2016-04-06 |
The contractible edges of a spanning tree and a perfect matching in k-connected graphs |
| |
| WANG Qian. The contractible edges of a spanning tree and a perfect matching in k-connected graphs[J]. Journal of Shandong University, 2016, 51(8): 29-34. DOI: 10.6040/j.issn.1671-9352.0.2016.148 |
| |
| Authors: | WANG Qian |
| |
| Affiliation: | School of Mathematics, Shandong University, Jinan 250100, Shandong, China |
| |
| Abstract: | The numbers of contractible edges of a spanning tree and a perfect matching in k-connected graphs are given. The conclusions are that if every fragment of a k-connected graph has an order more than 「k/2, then there exist at least four contractible edges on the spanning tree of this graph. Furthermore, if this graph has a perfect matching, then there exist at least 「k/2+1 contractible edges on the perfect matching. |
| |
| Keywords: | contractible edge perfect matching k-connect graph spanning tree |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 |
|
点击此处可从《山东大学学报(理学版)》下载全文 |
