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.