Convexity in Oriented Graphs



For vertices $u$ and $v$ in an oriented graph $D$, the closed interval $I[u, v]$ consists of $u$ and $v$ together with all vertices lying in a $u-v$ geodesic or $v-u$ geodesic in $D$. For $S \sbe V(D)$, $I[S]$ is the union of all closed intervals $I[u, v]$ with $u, v \in S$. A set $S$ is convex if $I[S] = S$. The convexity number $\con(D)$ is the maximum cardinality of a proper convex set of $V(D)$. The nontrivial connected oriented graphs of order $n$ with convexity number $n-1$ are characterized. It is shown that there is no connected oriented graph of order at least $4$ with convexity number $2$ and that every pair $k$, $n$ of integers with $1 \leq k \leq n-1$ and $k \neq 2$ is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph $G$, the lower orientable convexity number $\con^-(G)$ is the minimum convexity number among all orientations of $G$ and the upper orientable convexity number $\con^+(G)$ is the maximum such convexity number. It is shown that $\con^+(G) = n-1$ for every graph $G$ of order $n \geq 2$. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.