Up-Embeddability of a Graph by Order and Girth

摘要

Let G be a connected graph of order n and girth g. If d G (u) + d G (v) ≥ n ? 2g + 5 for any two non-adjacent vertices u and v, then G is up-embeddable. Further more, the lower bound is best possible. Similarly the result of k-edge connected simple graph with girth g is also obtained, k = 2,3.