On the Carathéodory number of interval and graph convexities. (English) Zbl 1419.05143
Summary: Inspired by a result of C. Carathéodory [Rend. Circ. Mat. Palermo 32, 193–217 (1911; JFM 42.0429.01)], the Carathéodory number of a convexity space is defined as the smallest integer \(k\) such that for every subset \(U\) of the ground set \(V\) and every element \(u\) in the convex hull of \(U\), there is a subset \(F\) of \(U\) with at most \(k\) elements such that \(u\) in the convex hull of \(F\). We study the Carathéodory number for generalized interval convexities and for convexity spaces derived from finite graphs. We establish structural properties, bounds, and hardness results.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 52A37 | Other problems of combinatorial convexity |
Keywords:
convexity space; Carathéodory number; interval convexity; geodetic convexity; monophonic convexity; \(P_3\)-convexityCitations:
JFM 42.0429.01References:
| [1] | Araujo, J.; Campos, V.; Giroire, F.; Sampaio, L.; Soares, R., On the hull number of some graph classes, Electron. Notes Discrete Math., 38, 49-55 (2011) · Zbl 1274.05120 |
| [2] | Barbosa, R. M.; Coelho, E. M.M.; Dourado, M. C.; Rautenbach, D.; Szwarcfiter, J. L., On the Carathéodory number for the convexity of paths of order three, SIAM J. Discrete Math., 26, 929-939 (2012) · Zbl 1256.05240 |
| [3] | Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L.; Seara, C., On geodetic sets formed by boundary vertices, Discrete Math., 306, 188-198 (2006) · Zbl 1084.05025 |
| [4] | Calder, J., Some elementary properties of interval convexities, J. Lond. Math. Soc., 3, 422-428 (1971) · Zbl 0228.52001 |
| [5] | Carathéodory, C., Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo, 32, 193-217 (1911) · JFM 42.0429.01 |
| [6] | Centeno, C. C.; Dantas, S.; Dourado, M. C.; Rautenbach, D.; Szwarcfiter, J. L., Convex partitions of graphs induced by paths of order three, Discrete Math. Theor. Comput. Sci., 12, 175-184 (2010) · Zbl 1280.68095 |
| [7] | Centeno, C. C.; Dourado, M. C.; Penso, L. D.; Rautenbach, D.; Szwarcfiter, J. L., Irreversible conversion of graphs, Theor. Comput. Sci., 412, 3693-3700 (2011) · Zbl 1220.05109 |
| [8] | Changat, M.; Klavžar, S.; Mulder, H. M., The all-paths transit function of a graph, Czech. Math. J., 51, 126, 439-448 (2001) · Zbl 0977.05135 |
| [9] | Changat, M.; Mathew, J., On triangle path convexity in graphs, Discrete Math., 206, 91-95 (1999) · Zbl 0929.05046 |
| [10] | Changat, M.; Mulder, H. M.; Sierksma, G., Convexities related to path properties on graphs, Discrete Math., 290, 117-131 (2005) · Zbl 1058.05043 |
| [11] | Changat, M.; Prasanth, G. N.; Mathews, J., Triangle path transit functions, betweenness and pseudo-modular graphs, Discrete Math., 309, 1575-1583 (2009) · Zbl 1228.05190 |
| [12] | Dourado, M. C.; Protti, F.; Rautenbach, D.; Szwarcfiter, J. L., On the hull number of triangle-free graphs, SIAM J. Discrete Math., 23, 2163-2172 (2010) · Zbl 1207.05044 |
| [13] | Dourado, M. C.; Protti, F.; Szwarcfiter, J. L., Complexity results related to monophonic convexity, Discrete Appl. Math., 158, 1269-1274 (2010) · Zbl 1209.05130 |
| [14] | Dourado, M. C.; Rautenbach, D.; Schäfer, P. M., On finite convexity spaces induced by sets of paths in graphs, Discrete Math., 311, 616-619 (2011) · Zbl 1216.05062 |
| [15] | Dragan, F.; Nicolai, F.; Brandstädt, A., Convexity and HHD-free graphs, SIAM J. Discrete Math., 12, 119-135 (1999) · Zbl 0916.05060 |
| [16] | Duchet, P., Convex sets in graphs II: Minimal path convexity, J. Comb. Theory, Ser. B, 44, 307-316 (1988) · Zbl 0672.52001 |
| [17] | Eckhoff, J., Helly, Radon, and Carathéodory type theorems, (Handbook of Convex Geometry, A, B (1993), North-Holland: North-Holland Amsterdam), 389-448 · Zbl 0791.52009 |
| [18] | Erdős, P.; Fried, E.; Hajnal, A.; Milner, E. C., Some remarks on simple tournaments, Algebra Univers., 2, 238-245 (1972) · Zbl 0267.05104 |
| [19] | Everett, M. G.; Seidman, S. B., The hull number of a graph, Discrete Math., 57, 217-223 (1985) · Zbl 0584.05044 |
| [20] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company · Zbl 0411.68039 |
| [21] | Harary, F.; Nieminen, J., Convexity in graphs, J. Differ. Geom., 16, 185-197 (1981) · Zbl 0493.05037 |
| [22] | Howorka, E., A characterization of distance-hereditary graphs, Quart. J. Math. Oxford, Ser. 2, 28, 417-420 (1977) · Zbl 0376.05040 |
| [23] | Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebr. Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056 |
| [24] | Farber, M.; Jamison, R. E., On local convexity in graphs, Discrete Math., 66, 231-247 (1987) · Zbl 0619.05032 |
| [25] | Moon, J. W., Embedding tournaments in simple tournaments, Discrete Math., 2, 389-395 (1972) · Zbl 0236.05108 |
| [26] | Parker, D. B.; Westhoff, R. F.; Wolf, M. J., On two-path convexity in multipartite tournaments, Eur. J. Comb., 29, 641-651 (2008) · Zbl 1141.05039 |
| [27] | Varlet, J. C., Convexity in tournaments, Bull. Soc. R. Sci. Liège, 45, 570-586 (1976) · Zbl 0351.05113 |
| [28] | van de Vel, M. L.J., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001 |
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.
