Convex Sets in Graphs
For two vertices $u$ and $v$ of a connected graph $G$, the set $I(u, v)$
consists of all those vertices lying on a $u-v$ geodesic in $G$. For a
set $S$
of vertices of $G$, the union of all sets $I(u,v)$ for $u, v \in S$ is
denoted by $I(S)$. A set $S$ is convex if $I(S) = S$.
The convexity number $\con(G)$ is
the maximum cardinality of a proper convex set of $G$.
A connected graph $G$ is polyconvex if for every integer
$i$ with $1 \leq i \leq \con (G)$, there exists a convex set
of cardinality $i$ in $G$.
Some well known polyconvex and nonpolyconvex graphs are determined.
It is shown that every pair $k, n$ of integers with
$2 \leq k \leq n-1$ is realizable
as the convexity number and order, respectively,
of some connected polyconvex graph.
Bounds for $\con (G) + \con (\overline{G})$ are discussed.
In this connection,
for positive integers $s, t$, the convex Ramsey number
$cr(s, t)$ is defined as the smallest positive integer $n$
such that for every graph $G$ of order
$n$, either $G$ contains a maximum convex set of cardinality $\geq s$ or
$\overline{G}$ contains a maximum convex set of cardinality $\geq t$.