The Forcing Hull Number of a Graph



For two vertices $u$ and $v$ of a connected graph $G$, the set $H(u, v)$ consists of all those vertices lying on a $u-v$ geodesic in $G$. Given a set $S$ of vertices of $G$, the union of all sets $H(u,v)$ for $u, v \in S$ is denoted by $H(S)$. A convex set $S$ satisfies $H(S) = S$. The convex hull $[S]$ is the smallest convex set containing $S$. The hull number $h(G)$ is the minimum cardinality among the subsets $S$ of $V(G)$ with $[S] = V(G)$. A set $S$ is a geodetic set if $H(S) = V(G)$; while $S$ is a hull set if $[S] = V(G)$. The minimum cardinality of a geodetic set of $G$ is the geodetic number $g(G)$. A subset $T$ of a minimum hull set $S$ is called a forcing subset for $S$ if $S$ is the unique minimum hull set containing $T$. The forcing hull number $f(S, h)$ of $S$ is the minimum cardinality among the forcing subsets of $S$, and the forcing hull number $f(G, h)$ of $G$ is the minimum forcing hull number among all minimum hull sets of $G$. The forcing geodetic number $f(S, g)$ of a minimum geodetic set $S$ in $G$ and the forcing geodetic number $f(G, g)$ of $G$ are defined in a similar fashion. The forcing hull numbers of several classes of graphs are determined. It is shown that for integers $a, b$ with $0 \leq a \leq b$, there exists a connected graph $G$ such that $f(G, h) = a$ and $h(G) = b$. We investigate the realizability of integers $a, b \geq 0$ that are the forcing hull and forcing geodetic numbers, respectively, of some graph.