顶点劈分与图的上可嵌入性(英文) |
| |
引用本文: | 董广华,王宁,黄元秋,任韩,刘彦佩.顶点劈分与图的上可嵌入性(英文)[J].数学进展,2014(5). |
| |
作者姓名: | 董广华 王宁 黄元秋 任韩 刘彦佩 |
| |
作者单位: | 湖南师范大学数学系;天津工业大学数学系;天津财经大学信息科学与技术系;华东师范大学数学系;北京交通大学数学系; |
| |
基金项目: | partially supported by the China Postdoctoral Science Foundation funded project(No.20110491248(G.Dong));the New Century Excellent Talents in University(No.NCET-07-0276(Y.Huang));NSFC(No.11171114(H.Ren),No.10871021(Y.Liu)) |
| |
摘 要: | 一个图G的弱子式G是通过对G进行边收缩得到的.一个弱子式封闭的上可嵌入图族是一个上可嵌入图的集合,并且该集合中任何图的弱子式仍在这个集合中.目前关于判断图的上可嵌入性的充要条件很少.本文通过研究顶点劈分与图的上可嵌入性的关系得出一个判断图的上可嵌入性的充要条件;给出了一个从环束出发构造弱子式封闭上可嵌入图族的方法;推广了J.Graph Theory,1981,5(2):205-207]的一个结论.并且,用本文所得结论判断图的上可嵌入性时其算法复杂度会得到很大降低.
|
关 键 词: | 最大亏格 弱图子式 柔性弱子式 柔性点 柔性边 |
本文献已被 CNKI 等数据库收录! |
|