// Workers AI · dad joke modeIs a convex subgraph curved up to the task?
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
[edit]- ↑ Bandelt & Chepoi (2008), 1. Basic notions, Convex and isometric subgraphs; Imrich & Klavžar (1998), p. 678.
- ↑ Bandelt & Chepoi (2008), discussion following Theorem 2.1.
References
[edit]- 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.
 | This graph theory-related article is a stub. You can help Wikipedia by adding missing information. |