The Convexity Number of a Graph



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$, while for a set $S$ of vertices of $G$, the set $I(S)$ is the union of all sets $I(u,v)$ for $u, v \in S$. A set $S$ is convex if $I(S) = S$. The convexity number $\con(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. The clique number $\om(G)$ is the maximum cardinality of a clique in $G$. A convex set of cardinality $\con(G)$ is called a maximum convex set, while a set of $\om(G)$ vertices that induces a clique is called a maximum clique set. If $G$ is a connected graph of order $n$ that is not complete, then $n \geq 3$ and $2 \leq \om(G) \leq \con(G) \leq n-1$. It is shown that for every triple $\ell, k,n$ of integers with $n \geq 3$ and $2 \leq \ell \leq k \leq n-1$, there exists a noncomplete connected graph $G$ of order $n$ with $\om (G) = \ell$ and $\con (G) = k$. Other results are presented concerning graphs containing maximum clique sets and maximum convex sets satisfying a variety of conditions.