Premium
The connectivity of the basis graph of a branching greedoid
Author(s) -
Broersma H. J.,
Xueliang Li
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160306
Subject(s) - mathematics , combinatorics , graph , connectivity , branching (polymer chemistry) , connected component , basis (linear algebra) , discrete mathematics , geometry , materials science , composite material
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.