The Forcing 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$. For a
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 a convex set if $I(S) = S$.
The convexity number $\con(G)$ of $G$ is
the maximum cardinality of a proper convex set of $G$.
A subset $T$ of a maximum convex set $S$ of a graph $G$ is
called a forcing subset for $S$ if $S$ is the unique maximum convex
set containing $T$. The forcing convexity number
$f(S, \con)$ of $S$ is the minimum
cardinality among the forcing subsets for $S$, and the forcing convexity
$f(G, \con)$ of $G$ is the minimum forcing convexity number
among all maximum convex sets of $G$.
The forcing convexity numbers of several classes of graphs
are presented, including complete bipartite graphs, trees, and cycles.
For every graph $G$,
$f(G, \con) \leq \con(G)$.
It is shown that every pair
$a, b$ of integers with $0 \leq a \leq b$ and $b \geq 3$ is realizable as
the forcing convexity number and convexity number, respectively, of some
The forcing convexity number of the Cartesian product of $H \times K_2$
for a nontrivial connected graph $H$ is studied.