✦ LIBER ✦

A remark on the connectivity of the complement of a 3-connected graph

✍ Scribed by Kiyoshi Ando; Atsusi Kaneko

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 413 KB
Volume: 151
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00078-w

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is said to be bi-3-connected if not only G but also its complement (~ are 3-connected and a two-vertex set whose contraction results in a bi-3-connected graph is called a bi-contractible pair of G. We prove that every bi-3-connected graph of order at least 22 has a bi-contractible pair.

📜 SIMILAR VOLUMES

The rainbow connectivity of a graph

✍ Gary Chartrand; Garry L. Johns; Kathleen A. McKeon; Ping Zhang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

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.

Lower-bounds on the connectivities of a

Lower-bounds on the connectivities of a graph

✍ Abdol H. Esfahanian 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 372 KB 👁 1 views

On the edge-connectivity vector of a gra

On the edge-connectivity vector of a graph

✍ Linda M. Lesniak; Raymond E. Pippert 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

2-connected 7-coverings of 3-connected g

2-connected 7-coverings of 3-connected graphs on surfaces

✍ Ken-ichi Kawarabayashi; Atsuhiro Nakamoto; Katsuhiro Ota 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

## Abstract An __m__‐__covering__ of a graph __G__ is a spanning subgraph of __G__ with maximum degree at most __m__. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus __k__ ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most

A remark on the number of vertices of de

A remark on the number of vertices of degree k in a minimally k-edge-connected graph

✍ Mao-cheng Cai 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 395 KB

Let G be a minimally k-edge-connected simple graph and u\*(G) be the number of vertices of degree k in G. proved that (i) uk(G) 2 l(jGl -1)/(2k + l)] + k + 1 for even k, and (ii) uI(G) 2 [lGl/(k + l)] + k for odd k 35 and u,(G) 2 lZlGl/(k + l)] + k -2 for odd k 27, where ICI denotes the number of v