On Graphs With a Unique Minimum Hull Set



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 set $S$ 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$ and is a geodetic set if $I(S) = V(G)$. The geodetic number $g(G)$ is the minimum cardinality of a geodetic set. The convex hull $[S]$ is the smallest convex set containing $S$. A set $S$ of vertices of $G$ is a hull set if $[S] = V(G)$. A hull set of $G$ of minimum cardinality is a minimum hull set and its cardinality is the hull number $h(G)$. A graph $G$ with a unique minimum hull set is called a hull graph. The link $L(v)$ of a vertex $v$ in a graph $G$ is the subgraph of $G$ induced by the neighbors of $v$. A vertex $v$ in $G$ is an extreme vertex if $L(v)$ is complete. Each extreme vertex of $G$ belongs to every hull set and every geodetic set of $G$. A vertex $v$ of $G$ is a hull vertex if it belongs to every hull set in $G$. It is shown that for every integer $k \geq 2$ and every $k$ graphs $G_1, G_2, \cdots, G_k$, there exists a hull graph $G$ with $k$ hull vertices $v_1, v_2, \cdots v_k$ with $L(v_i) = G_i$ for $1 \leq i \leq k$. A set $S$ of vertices in a connected graph $G$ is a minimal geodetic set if $S$ is a geodetic set but no proper subset of $S$ is a geodetic set. The upper geodetic number $g^+(G)$ is the maximum cardinality of a minimal geodetic set of $G$. Hence, $h(G) \leq g(G) \leq g^+(G)$. For a minimum geodetic set $S$ of $G$, a subset $T$ of $S$ with the property that $S$ is the unique minimum geodetic set containing $T$ is called a forcing subset of $S$. The forcing geodetic number $f(S, g)$ of $S$ is the minimum cardinality of a forcing subset for $S$, while the forcing geodetic number $f(G, g)$ of $G$ is the smallest forcing number among all minimum geodetic sets of $G$. It is shown that every pair $a, b $ of integers with $2 \leq a \leq b$ is realizable as the hull number and geodetic number (or upper geodetic number) of a hull graph. It also shown that every pair $a, b $ of integers with $a \geq 2$ and $b \geq 0$ is realizable as the hull number and forcing geodetic number of a hull graph.