Nielsen, Morten H.; Oellermann, Ortrud R. Helly theorems for 3-Steiner and 3-monophonic convexity in graphs. (English) Zbl 1223.05158 Discrete Math. 311, No. 10-11, 872-880 (2011). Summary: A family \(\mathcal C\) of sets has the Helly property if any subfamily \(\mathcal C^\prime \) whose elements are pairwise intersecting has non-empty intersection. Suppose that \(\mathcal C\) is a non-empty family of subsets of a finite set \(V\): the Helly number \(h(\mathcal C)\) of \(\mathcal C\) is the least positive integer \(n\) such that every \(n\)-wise intersecting subfamily of \(\mathcal C\) has non-empty intersection . In this paper the Helly property of families of convex sets relative to two new graph convexities are studied. Let \(G\) be a (finite) connected graph and \(U\) a set of vertices of \(G\). A connected subgraph with the fewest edges containing \(U\) is called a Steiner tree for \(U\), and the collection of all vertices of \(G\) that belong to some Steiner tree for \(U\) is called the Steiner interval for \(U\). A set \(S\) of vertices of \(G\) is \(g_{3}\)-convex if it contains the Steiner interval for every 3-subset \(U\) of \(S\). A subtree \(T\) of \(G\) that contains \(U\) is a minimal \(U\)-tree if every vertex of \(T\) that is not in \(U\) is a cut-vertex of the subgraph induced by \(V(T)\). The set of all vertices that belong to some minimal \(U\)-tree is called the monophonic interval for \(U\) and a set \(S\) of vertices is \(m_{3}\)-convex if it contains the monophonic interval of every 3-subset \(U\) of \(S\). Those graphs are characterized for which the families of \(g_{3}\)-convex (\(m_{3}\)-convex) sets of size at least 3 have the Helly property. A graph obtained from a complete graph by deleting a matching is called a near-clique. The maximum order of a near-clique in a graph \(G\) is called the near-clique number of \(G\). The near-clique number of a graph is a lower bound on the Helly number for both \(g_{3}\)-convex families and \(m_{3}\)-convex families. For \(m_{3}\)-convex families equality holds. For \(g_{3}\)-convex families equality holds for chordal graphs and for distance-hereditary graphs, but the bound can be arbitrarily bad in general, even when the near-clique number is 3. Cited in 3 Documents MSC: 05C40 Connectivity 05C38 Paths and cycles 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C05 Trees Keywords:Helly number; Helly property; Steiner tree; minimal \(U\)-tree; convexity PDFBibTeX XMLCite \textit{M. H. Nielsen} and \textit{O. R. Oellermann}, Discrete Math. 311, No. 10--11, 872--880 (2011; Zbl 1223.05158) Full Text: DOI References: [1] Bandelt, H.-J.; Chepoi, V., A Helly theorem in weakly modular space, Discrete Math., 160, 25-39 (1996) · Zbl 0864.05049 [2] Bandelt, H.-J.; Mulder, H. M., Helly theorems for dismantlable graphs and pseudo-modular graphs, (Topics in Combinatorics and Graph Theory (1990), Physica-Verlag: Physica-Verlag Heidelberg), 65-71 · Zbl 0697.05034 [3] Bandelt, H.-J.; Mulder, H. M., Distance-hereditary graphs, J. Combin. Theory Ser. B, 41, 182-208 (1986) · Zbl 0605.05024 [4] Bandelt, H.-J.; Pesch, E., A Radon theorem for Helly graphs, Arch. Math., 52, 95-98 (1989) · Zbl 0677.52001 [5] A. Brandstädt, V.B. Le, J.P. Spinrad, Graph classes: a survey, in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 1999.; A. Brandstädt, V.B. Le, J.P. Spinrad, Graph classes: a survey, in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 1999. [6] Cáceres, J.; Oellermann, O. R., On 3-Steiner simplicial orderings, Discrete Math., 309, 5828-5833 (2009) · Zbl 1221.05042 [7] Chartrand, G.; Oellermann, O. R.; Tian, S. L.; Zou, H. B., Steiner distance in graphs, Časopis Pěst. Mat., 114, 399-410 (1989) · Zbl 0688.05040 [8] M. Chastand, Théorème de Helly pour les graphes quasi-médians, Papier de recherche, n. 6-IAE, 1993.; M. Chastand, Théorème de Helly pour les graphes quasi-médians, Papier de recherche, n. 6-IAE, 1993. [9] Chepoi, V., Some properties of \(d\)-convexity in triangulated graphs, Math. Issledovanija, 87, 167-177 (1986), (in Russian) [10] Day, D.; Oellermann, O. R.; Swart, H. C., Steiner distance-hereditary graphs, SIAM J. Discrete Math., 7, 437-442 (1994) · Zbl 0805.05021 [11] Dirac, G., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703 [12] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Alg. Discrete Meth., 7, 433-444 (1986) · Zbl 0591.05056 [13] Hajnal, A.; Surányi, J., Über die Auflösung von Graphen in vollständige Teilgraphen, Ann. Univ. Sci. Budapest, Eötvös Sect. Math., 1, 113-121 (1958) · Zbl 0093.37801 [14] Helly, E., Über Mengen konvexer Körper mit gemeinschaftlichen Punkter, Jahresber. Deutsch. Math.-Verein., 32, 175-176 (1923) · JFM 49.0534.02 [15] Howorka, E., A characterization of distance-hereditary graphs, Quart. J. Math. Oxford Ser. 2, 28, 417-420 (1977) · Zbl 0376.05040 [16] Jamison, R. E.; Nowakowski, R., A Helly theorem for convexity in graphs, Discrete Math., 51, 35-39 (1984) · Zbl 0548.05052 [17] Kubicka, E.; Kubicki, G.; Oellermann, O. R., Steiner intervals in graphs, Discrete Appl. Math., 81, 181-190 (1998) · Zbl 0898.05044 [18] Nielsen, M. H.; Oellermann, O. R., Steiner trees and convex geometries, SIAM J. Discrete Math., 23, 680-693 (2009) · Zbl 1191.05037 [19] Oellermann, O. R.; Puertas, M. L., Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs, Discrete Math., 307, 88-96 (2007) · Zbl 1113.05030 [20] Polat, N., A Helly theorem for geodesic convexity in strongly dismantlable graphs, Discrete Math., 140, 119-127 (1995) · Zbl 0828.05062 [21] Polat, N., On constructible graphs, locally Helly graphs, and convexity, J. Graph Theory, 43, 280-298 (2003) · Zbl 1023.05044 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.