顶点劈分与图的上可嵌入性(英文)

Vertex Splitting and Upper Embeddable Graphs

一个图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.