✦ LIBER ✦

On Paths of Greedoids and a Minor Characterization

✍ Scribed by Erhard Hexel

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 156 KB
Volume: 15
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1994.1025

No coin nor oath required. For personal study only.

✦ Synopsis

Let (p_{n}) denote the maximum number of paths a greedoid over (n) elements can have. As an upper bound, we of course have (p_{n}<2^{n}). We establish a lower bound for the maximum: (1.6 \cdot 3^{n / 3}<p_{n}). In the class of simple greedoids (those greedoids on (n) elements having exactly (n) paths), we provide an excluded minor characterization of simple interval greedoids: a simple greedoid is an interval greedoid iff it has no minor isomorphic to (\left.2^{{a, b, c h}\right}{a, c}).

📜 SIMILAR VOLUMES

Minor characterization of undirected bra

Minor characterization of undirected branching greedoids—a short proof

✍ Oskar Goecke; Rainer Schrader 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 433 KB

In 1959 Tutte gave a minor characterization of graphic matroids. Within the framework of greedoids, a natural analogue of the cycle matroid in graphs is the branching greedoid. Schmidt has shown that, similar to Tutte's result, branching greedoids can be characterized by forbidden minors. Here we g

A Characterization of Mixed Branching Gr

A Characterization of Mixed Branching Greedoids

✍ Steven J. Tedford 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 211 KB

On the characterization of path graphs

✍ Huaien Li; Yixun Lin 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB

## Abstract Broersma and Hoede have introduced path graphs. Their characterization of __P__~3~‐graphs contains a flaw. This note presents the correct form of the characterization. © 1993 John Wiley & Sons, Inc.

A characterization of graphs without lon

A characterization of graphs without long induced paths

✍ Gábor Bacsó; Zsolt Tuza 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB 👁 1 views

## Abstract In a connected graph define the k‐center as the set of vertices whose distance from any other vertex is at most __k.__ We say that a vertex set __S__ __d__‐dominates __G__ if for every vertex x there is a y ∈ __S__ whose distance from __x__ is at most __d__. Call a graph __P~t~__‐free

A Characterization of Graphs with No Cub

A Characterization of Graphs with No Cube Minor

✍ John Maharry 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 418 KB

In this paper it is shown that any 4-connected graph that does not contain a minor isomorphic to the cube is a minor of the line graph of V n for some n 6 or a minor of one of five graphs. Moreover, there exists a unique 5-connected graph on at least 8 vertices with no cube minor and a unique 4-conn

A forbidden minor characterization and r

A forbidden minor characterization and reliability of a class of partial 4-trees

✍ Gerard T. Lingner; Themistocles Politof; A. Satyanarayana 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 801 KB