|
Classes of Upper Embeddable Graphs with Specific Minimum Degree-Sum of Vertices in Independent-Set(English)
GAO Yan-bo;REN Han
2006, 2006 (3):
37-43.
Combined with the edge-connectivity, this paper investigated the upper embeddable graphs with specific minimum degree-sum of vertices in its independent-set, and obtained the following results. (1) Let G be a 2-edge-connected simple graph, if G satisfies the following conditions: for any 3-independent set I in G, ∨xi ,xj ∈I (i,j = 1,2,3), d(xi ,xj)≧3 (1 ≦ i ≠ j ≦ 3) => ∑i = 13 d(xi) ≧ v + 1(v = | V(G)|}), then G is upper embeddable; (2) Let G be 3-edge-connected simple graph, if G satisfies the following conditions: for any 6-independent set I in G, ∨xi ,xj ∈I (1≦i,j≦6), d(xi,xj) ≧3(1 ≦ i ≠ j ≦ 6) => ∑i = 16 d(xi) ≧ v + 1(v = | V(G)|), then G is upper embeddable.
Related Articles |
Metrics
|