Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: minimal trees

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Minimal trees and monophonic convexity

100%

Cáceres J., Oellermann O., Puertas M.

Discussiones Mathematicae Graph Theory

2012

tom 32

nr 4

685-704

Let V be a finite set and 𝓜 a collection of subsets of V. Then 𝓜 is an alignment of V if and only if 𝓜 is closed under taking intersections and contains both V and the empty set. If 𝓜 is an alignment of V, then the elements of 𝓜 are called convex sets and the pair (V,𝓜 ) is called an alignment or a convexity. If S ⊆ V, then the convex hull of S is the smallest convex set that contains S. Suppose X ∈ ℳ. Then x ∈ X is an extreme point for X if X∖{x} ∈ ℳ. A convex geometry on a finite set is an aligned space with the additional property that every convex set is the convex hull of its extreme points. Let G = (V,E) be a connected graph and U a set of vertices of G. A subgraph T of G containing U is a minimal U-tree if T is a tree and if every vertex of V(T)∖U is a cut-vertex of the subgraph induced by V(T). The monophonic interval of U is the collection of all vertices of G that belong to some minimal U-tree. Several graph convexities are defined using minimal U-trees and structural characterizations of graph classes for which the corresponding collection of convex sets is a convex geometry are characterized.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Cáceres J.

1 Oellermann O.

1 Puertas M.

1 2012

Wyniki wyszukiwania

Minimal trees and monophonic convexity