The Forcing Hull Number of a Graph

Abstract

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\le a\le 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\ge 0$ that are the forcing hull and forcing geodetic numbers, respectively, of some graph.