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

【Abstract】 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 a graph in faces of an embedding of another graph in a surface.更多还原