Convex sets in graphs. II: Minimal path convexity (Q1120125)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Convex sets in graphs. II: Minimal path convexity |
scientific article |
Statements
Convex sets in graphs. II: Minimal path convexity (English)
0 references
1988
0 references
[For part I see the author and \textit{H. Meyniel}, Eur. J. Comb. 4, 127-132 (1983; Zbl 0523.05031).] The basic structure is a graph-convexity space (G,\({\mathcal C})\) with G a connected graph with vertex set V, and \({\mathcal C}^ a \)convexity structure on V such that (a) \(\emptyset,V\in {\mathcal C}\), (b) \({\mathcal C}\) is closed under arbitrary intersections, (c) \({\mathcal C}\) is closed under nested unions, and (d) every member of \({\mathcal C}\) induces a connected subgraph of G. The minimal path convexity can be defined by an interval function I: \(V\times V\to 2^ V\) with I(x,y) the set of all vertices of all chordless (x,y)-paths; the elements of \({\mathcal C}\) then are those sets which are closed under the operator I. The goal of this paper is to show how particular minimal path convexity spaces are by determining the exact values of the Carathéodory, Helly and Radon numbers.
0 references
Carathéodory number
0 references
Radon number
0 references
Helly number
0 references
graph-convexity
0 references
minimal path convexity spaces
0 references