Upper Embeddability, Girth and the Degree-Sum of Nonadjacent Vertices

摘要

Let G be a 2-edge-connected simple graph with girth g, independence number alpha(G), and if one of the following two conditions holds (1) alpha(G) <= 2; (2) alpha(G) >= 3, and for any three nonadjacent vertices v(i) (i = 1, 2, 3), it has Sigma(3)(i=1) d(G)(v(i)) >= v - 3g + 7, then G is upper embeddable and the lower bound v - 3g + 7 is best possible. Similarly the result for 3-edge-connected simple graph with girth g and independence number alpha(G) is also obtained.