图的上可嵌入性的邻域条件

NEIGHBORING CONDITION ON UPPER EMBEDDABILITY OF GRAPHS

用NG（u）表示一个图G中任意点u的邻域集．本文主要证明了下述结果：设G是无环图，对G中任意相邻的点u和υ，即uυ∈E（G），若如下两条件之一满足：（1）|NG(u)∩NG(υ)≥2;（2）G是2-点连通的图，且|NG(u)∩NG(υ)|≥1,则G是上可嵌入的．

Let NG(u) denote the neighboring set of a vertex u in G. This paper mainly proves the following result: let G be a graph without loops, for any two adjacent vertices u and v of G, i.e., uv E E(G), if at least one of the following two conditions satisfies: (1)|NG(u)∩NG(υ)≥2; (2) G is 2-vertex-connected graph and|NG(u)∩NG(υ)|≥1 , then G is upper embeddable.