Convex subgraph

In this graph, triangle 1-2-5 is convex, but path 2-3-4 is not, because it does not include one of the two shortest paths from 2 to 4.

In metric graph theory, a convex subgraph of an undirected graph G is a subgraph that includes every shortest path in G between two of its vertices. Thus, it is analogous to the definition of a convex set in geometry, a set that contains the line segment between every pair of its points.^[1]

Convex subgraphs play an important role in the theory of partial cubes and median graphs. In particular, in median graphs, the convex subgraphs have the Helly property: if a family of convex subgraphs has the property that all pairwise intersections are nonempty, then the whole family has a nonempty intersection.^[2]

Notes

1. Bandelt & Chepoi (2008), 1. Basic notions, Convex and isometric subgraphs; Imrich & Klavžar (1998), p. 678.
2. Bandelt & Chepoi (2008), discussion following Theorem 2.1.

References

• Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey" (PDF), in Goodman, J. E.; Pach, J.; Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary Mathematics, vol. 453, Providence, RI: AMS, pp. 49–86.
• Imrich, Wilfried; Klavžar, Sandi (1998), "A convexity lemma and expansion procedures for bipartite graphs", European Journal of Combinatorics, 19 (6): 677–686, doi:10.1006/eujc.1998.0229, MR 1642702.