A Helly theorem for convexity in graphs
type: Item
instance of: scholarly article
title: A Helly theorem for convexity in graphs
zbMATH Open document ID: 0548.05052
DOI: 10.1016/0012-365X(84)90021-9
author: Robert E. Jamison
author: R. J. Nowakowski
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: A set K of nodes of a (finite, simple, loopless, undirected) graph G is called m-convex (geodesically convex) if for each pair x, y of nodes of K all nodes on chordless (shortest) paths joining x and y are also in K. The authors prove that for any connected G the Helly number of the m- convex sets equals the clique number of G, while an analogous result for geodesically convex sets does not hold.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 52A35
zbMATH DE Number: 3873381
zbMATH Keywords: abstract convexity
zbMATH Keywords: Helly number
zbMATH Keywords: clique number
zbMATH Keywords: geodesically convex sets
reviewed by: Christoph Schulz
MaRDI profile type: Publication
cites work: Q5341481
cites work: Ensemble convexes dans les graphes. I: Théoremes de Helly et de Radon pour graphes et surfaces
cites work: Q3889702
cites work: The edge inducibility of graphs
cites work: Q3951161
cites work: Partition numbers for trees and ordered sets
cites work: Q3940405
cites work: Q3890733
cites work: Some aspects of perfect elimination orderings in chordal graphs
full work available at URL: 0012-365x(84)90021-9
OpenAlex ID: W2063849229
description: scientific article; zbMATH DE number 3873381