𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The connectivity of the basis graph of a branching greedoid

✍ Scribed by H. J. Broersma; Li Xueliang

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
273 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A result of Korte and LovΓ‘sz states that the basis graph of every 2‐ connected greedoid is connected. We prove that the basis graph of every 3‐connected branching greedoid is (Ξ΄ ‐‐ 1)‐connected, where Ξ΄ is the minimum in‐degree (disregarding the root) of the underlying rooted directed (multi) graph. We also give examples showing that this results is (in some sense) best possible.

πŸ“œ SIMILAR VOLUMES

The rainbow connectivity of a graph
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
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
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.

A remark on the connectivity of the comp
A remark on the connectivity of the complement of a 3-connected graph
✍ Kiyoshi Ando; Atsusi Kaneko πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 413 KB

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.