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