摘要
一个图G的弱子式G是通过对G进行边收缩得到的.一个弱子式封闭的上可嵌入图族是一个上可嵌入图的集合,并且该集合中任何图的弱子式仍在这个集合中.目前关于判断图的上可嵌入性的充要条件很少.本文通过研究顶点劈分与图的上可嵌入性的关系得出一个判断图的上可嵌入性的充要条件;给出了一个从环束出发构造弱子式封闭上可嵌入图族的方法;推广了[J.Graph Theory,1981,5(2):205-207]的一个结论.并且,用本文所得结论判断图的上可嵌入性时其算法复杂度会得到很大降低.
The weak minor G of a graph G is the graph obtained from G by a sequence of edge-contraction operations on G.A weak-minor-closed family of upper embeddable graphs is a set g of upper embeddable graphs that for each graph G in G,every weak minor of G is also in g.Up to now,there are few results providing the necessary and sufficient conditions for characterizing upper embeddability of graphs.In this paper,we study the relation between the vertex splitting operation and the upper embeddability of graphs;provide not only a necessary and sufficient condition for characterizing upper embeddability of graphs,but also a way to construct weak-minor-closed family of upper embeddable graphs from the bouquet of circles;and extend a result in[J.Graph Theory,1981,5(2):205-207].In addition,the algorithm complex of determining the upper embeddability of a graph can be reduced much by the results obtained in this paper.
出处
《数学进展》
CSCD
北大核心
2014年第5期711-724,共14页
Advances in Mathematics（China）
基金
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))
关键词
最大亏格
弱图子式
柔性弱子式
柔性点
柔性边
maximum genus
weak minor
flexible-weak-minor
flexible-vertex
flexibleedge
