| Abstrakt: |
Let Gbe a 2‐edge‐connected undirected graph, Abe an (additive) abelian group and A* = A−{0}. A graph Gis A‐connected if Ghas an orientation D(G) such that for every function b: V(G)↦Asatisfying , there is a function f: E(G)↦A* such that for each vertex v∈V(G), the total amount of fvalues on the edges directed out from vminus the total amount of fvalues on the edges directed into vequals b(v). For a 2‐edge‐connected graph G, define Λg(G) = min{k: for any abelian group Awith |A|⩾k, Gis A‐connected }. In this article, we prove the following Ramsey type results on group connectivity: Let Gbe a simple graph on n⩾6 vertices. If min{δ(G), δ(Gc)}⩾2, then either Λg(G)⩽4, or Λg(Gc)⩽4.Let Z3denote the cyclic group of order 3, and Gbe a simple graph on n⩾44 vertices. If min{δ(G), δ(Gc)}⩾4, then either Gis Z3‐connected, or Gcis Z3‐connected. © 2011 Wiley Periodicals, Inc. J Graph Theory |
Plný text