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$.