一个不可定向曲面的极小禁用子图的构造

Generating Minimal Forbidden Subgraphs for a Non-Orientable Surface

曲面S的一个极小禁用子图是这样的一个图,它的任何一个顶点的度都不小于3,它不能嵌入在S上,但是删去任何一条边后得到的图能嵌入在S上.本文给出了四种构造一个不可定向曲面的极小禁用子图的方式,即粘合一个顶点,一个图的边被其它的图替换,粘合两个顶点,将一个图放在另一个图的一个曲面嵌入的面内.

A graph G is a minimal forbidden subgraph for a surface S if G has no vertices with degree less than three, and if G is not embeddable in S but G - e is embeddable in S for any edge e of G. In the paper we give four methods generating minimal forbidden subgraphs for a non-orientable surface, i.e., amalgamating a vertex, edges of a graph replaced by other graphs, amalgamating two vertices and placing agraph in faces of an embedding of another graph in a surface.