Group connectivity of complementary graphs |
| |
| Authors: | Xinmin Hou Hong‐Jian Lai Ping Li Cun‐Quan Zhang |
| |
| Institution: | 1. Department of Mathematics, University of Science and Technology of China, , Hefei, 230026 People's Republic of China;2. College of Mathematics and System Sciences, Xinjiang University, , Xinjiang, 830046 People's Republic of China;3. Department of Mathematics West Virginia University, , Morgantown, West Virginia, 26506 |
| |
| Abstract: | Let G be a 2‐edge‐connected undirected graph, A be an (additive) abelian group and A* = A?{0}. A graph G is A‐connected if G has an orientation D(G) such that for every function b: V(G)?A satisfying  , there is a function f: E(G)?A* such that for each vertex v∈V(G), the total amount of f values on the edges directed out from v minus the total amount of f values on the edges directed into v equals b(v). For a 2‐edge‐connected graph G, define Λg(G) = min{k: for any abelian group A with |A|?k, G is A‐connected }. In this article, we prove the following Ramsey type results on group connectivity: - Let G be a simple graph on n?6 vertices. If min{δ(G), δ(Gc)}?2, then either Λg(G)?4, or Λg(Gc)?4.
- Let Z3 denote the cyclic group of order 3, and G be a simple graph on n?44 vertices. If min{δ(G), δ(Gc)}?4, then either G is Z3‐connected, or Gc is Z3‐connected. © 2011 Wiley Periodicals, Inc. J Graph Theory
|
| |
| Keywords: | |
|
|
