Convex sets in graphs. II: Minimal path convexity. (English) Zbl 0672.52001
[For part I see the author and 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.
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.
Reviewer: G.Sierksma
MSC:
| 52A01 | Axiomatic and generalized convexity |
| 52A35 | Helly-type theorems and geometric transversal theory |
| 05C40 | Connectivity |
Keywords:
Carathéodory number; Radon number; Helly number; graph-convexity; minimal path convexity spacesCitations:
Zbl 0523.05031References:
| [1] | Bean, P. W., Helly and Radon-type theorems in interval convexity spaces, Pacific J. Math., 51, 363-368 (1979) · Zbl 0285.52005 |
| [2] | Berge, C.; Duchet, P., A generalization of Gilmore’s theorem, (Recent Advances in Graph Theory. Recent Advances in Graph Theory, Proceedings, 2nd Czckoslowack Symposium, Prague (1975)), 49-55 · Zbl 0325.05125 |
| [3] | Bryant, V. W.; Webster, R. J., Convexity spaces. I. The basic properties, J. Math. Anat. Appl., 37, 206-213 (1972) · Zbl 0197.48401 |
| [4] | Calder, J., Some elementary properties of interval convexities, J. London Math. Soc., 3, 2, 422-428 (1971) · Zbl 0228.52001 |
| [5] | Cochand, M.; Duchet, P., Sous les pavés…, (Proc. Marseille-Luminy Coll.. Proc. Marseille-Luminy Coll., Ann. Discrete Math., 17 (1983)), 191-202 · Zbl 0522.52001 |
| [6] | Cohn, P. M., (Universal Algebra (1965), Reidel: Reidel Dordrecht/Boston/London), rev. ed., 1981 |
| [7] | Duchet, P., Représentations, Noyaux en théorie des graphes et des hypergraphes, (Thèse (1979), Université Paris 6) |
| [8] | Duchet, P.; Meyniel, H., Ensembles convexes dans les graphes, I: theorèmes de Helly et de Radon pour graphes et surfaces, European J. Combin., 4, 127-132 (1983) · Zbl 0523.05031 |
| [9] | P. Duchet; P. Duchet |
| [10] | Duchet, P., Propriété de Helly et problèmes de représentation, (Problèmes combinatoires et théorie des graphes. Problèmes combinatoires et théorie des graphes, Coll. Int. CNRS 260 (Orsay 1976) (1978), CNRS: CNRS Paris), 117-118 · Zbl 0413.05042 |
| [11] | Duchet, P., Convexity in combinatorial structures, Res. Rep. Univ. Paris 6 (1986), Rend. Circ. Mat. Palermo, in press |
| [12] | Eckhoff, J., Radon’s theorem revisited, (Todke, J.; Mills, I. M., Contributions to Geometry. Contributions to Geometry, Proceedings, Geom. Symp. Siegen, 1978 (1979), Birkhaüser-Verlag: Birkhaüser-Verlag Basel), 164-185 · Zbl 0445.52009 |
| [13] | J. Eckhoff; J. Eckhoff · Zbl 0445.52009 |
| [14] | Edelman, P. H.; Jamison, R. E., The theory of convex geometries, Geom. Dedicata, 19, 247-270 (1985) · Zbl 0577.52001 |
| [15] | Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, (Report CURR (1983), University of Waterloo), 83 |
| [16] | Jamison, R., Partition numbers for trees and ordered sets, Pacific J. Math., 96, 115-140 (1981) · Zbl 0482.52010 |
| [17] | Jamison-Waldner, R., A perspective on abstract convexity: Classifying alignements by varieties, (Kay, D.; Breen, M., Convexity and Related Combinatorial Geometry (1982), Decker: Decker New York), 113-150 · Zbl 0482.52001 |
| [18] | Jamison, R. E.; Nowakowski, R., A Helly theorem for convexity in graphs, Discrete Math., 51, 35-39 (1984) · Zbl 0548.05052 |
| [19] | Kay, D.; Womble, E. W., Axiomatic convexity theory and relationships between the Carathéodory, Helly and Radon numbers, Pacific J. Math., 38, 471-485 (1971) · Zbl 0235.52001 |
| [20] | Levi, F. W., On Helly’s theorem and the axioms of convexity, J. Indian Math. Soc. (N.S.), 15, 65-76 (1951) · Zbl 0044.19101 |
| [21] | Mulder, H. M., The Interval Function of a Graph, Dissertation (1980), Math. Centre Tracts 132, Amsterdam · Zbl 0446.05039 |
| [22] | Schmidt, J., Über die Rolle des transfiniten Schlussweisen in einer allgemeinen Ideal theorie, Math. Nachr., 7, 165-182 (1952) · Zbl 0049.16601 |
| [23] | Sierksma, G., Relationships between Cartheodory, Helly, Radon, and exchange numbers of convexity spaces, Nieuw Arch. Wisk., 25, 3, 115-132 (1977) · Zbl 0354.52005 |
| [24] | Soltan, V. P., (Introduction to Axiomatic Convexity Theory (1984), Chtiitsa: Chtiitsa Kichiniev), [in Russian] · Zbl 0559.52001 |
| [25] | Valentine, F. A., (Convex Sets (1964), McGraw-Hill: McGraw-Hill New York) · Zbl 0129.37203 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
