𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Group connectivity of complementary graphs

✍ Scribed by Xinmin Hou; Hong-Jian Lai; Ping Li; Cun-Quan Zhang

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
113 KB
Volume
69
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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), δ(G^c^)}⩾2, then either Λ~g~(G)⩽4, or Λ~g~(G^c^)⩽4.

Let Z~3~ denote the cyclic group of order 3, and G be a simple graph on n⩾44 vertices. If min{δ(G), δ(G^c^)}⩾4, then either G is Z~3~‐connected, or G^c^ is Z~3~‐connected. © 2011 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Hamilton-Connected Cayley Graphs on Hami
Hamilton-Connected Cayley Graphs on Hamiltonian Groups
✍ Brian Alspach; Yusheng Qin 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 109 KB

It is proven that every connected Cayley graph X , of valency at least three, on a Hamiltonian group is either Hamilton laceable when X is bipartite, or Hamilton connected when X is not bipartite.

The Connectivities of Leaf Graphs of 2-C
The Connectivities of Leaf Graphs of 2-Connected Graphs
✍ Atsushi Kaneko; Kiyoshi Yoshimoto 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 286 KB

Given a connected graph G, denote by V the family of all the spanning trees of G. Define an adjacency relation in V as follows: the spanning trees t and t$ are said to be adjacent if for some vertex u # V, t&u is connected and coincides with t$&u. The resultant graph G is called the leaf graph of G.

The connectivity of minimal imperfect gr
The connectivity of minimal imperfect graphs
✍ Seb�, Andr�s 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 535 KB

We prove that partitionable graphs are 2w -2-connected, that this bound is sharp, and prove some structural properties of cutsets of cardinality 2w -2. The proof of the connectivity result is a simple linear algebraic proof.

Hamilton connectivity of line graphs and
Hamilton connectivity of line graphs and claw-free graphs
✍ Zhiquan Hu; Feng Tian; Bing Wei 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Let __G__ be a graph and let __V__~0~ = {ν∈ __V__(__G__): __d__~__G__~(ν) = 6}. We show in this paper that: (i) if __G__ is a 6‐connected line graph and if |__V__~0~| ≤ 29 or __G__[__V__~0~] contains at most 5 vertex disjoint __K__~4~'s, then __G__ is Hamilton‐connected; (ii) every 8‐co