Connectivity of the lifts of a greedoid

Steven J. Tedford

The electronic journal of combinatorics, Tome 14 (2007)

Résumé

Recently, attempts were made to generalize the undirected branching greedoid to a greedoid whose feasible sets consist of sets of edges containing the root satisfying additional size restrictions. Although this definition does not always result in a greedoid, the lift of the undirected branching greedoid has the properties desired by the authors. The $k$-th lift of a greedoid has sets whose nullity is at most $k$ in the original greedoid. We prove that if the greedoid is $n$-connected, then its lift is also $n$-connected. Additionally, for any cut-vertex $v$ and cut-edge $e$ of a graph $\Gamma$, let $C(v)$ be the component of $\Gamma\setminus v$ containing the root and $C(e)$ be the component of $\Gamma\setminus e$ containing the root. We prove that if the $k$-th lift of the undirected branching greedoid is 2-connected, then $$\eqalign{ |{E(C(v))}|& < |{V(C(v))}|+k-1\hbox{ and }\cr |{E(C(e))}|&>|{E(\Gamma)}|-{k}-2.\cr }$$ We also give examples indicating that no sufficient conditions for the $k$th lift to be 2-connected exists similar to these necessary conditions.

Détail

DOI : 10.37236/1010

Classification : 05B35
Mots-clés : undirected branching greedoid