In metric
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a convex subgraph of an undirected graph ''G'' is a subgraph that includes every
shortest path
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between tw ...
in ''G'' between two of its vertices. Thus, it is analogous to the definition of a
convex set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...
in geometry, a set that contains the line segment between every pair of its points.
Convex subgraphs play an important role in the theory of
partial cube
In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cu ...
s and
median graph
In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pair o ...
s. In particular, in median graphs, the convex subgraphs have the
Helly property
In combinatorics, a Helly family of order is a family of sets in which every minimal ''subfamily with an empty intersection'' has or fewer sets in it. Equivalently, every finite subfamily such that every -fold intersection is non-empty has non ...
: if a family of convex subgraphs has the property that all pairwise intersections are nonempty, then the whole family has a nonempty intersection.
References
*.
*.
Graph theory
{{graph-stub