Geodomination in Graphs



A pair $x, y$ of vertices in a nontrivial connected graph $G$ is said to geodominate a vertex $v$ of $G$ if either $v \in \{x, y\}$ or $v$ lies in an $x-y$ geodesic of $G$. A set $S$ of vertices of $G$ is a geodominating set if every vertex of $G$ is geodominated by some pair of vertices of $S$. The cardinality of a minimum geodominating set in $G$ is the geodomination number $g(G)$. The pair $x, y$ openly geodominates $v$ if $v \neq x, y$ and $v$ is geodominated by $x$, $y$. A vertex $v$ is link-complete in $G$ if the subgraph induced by its neighborhood is complete. A set $S$ is an open geodominating set of $G$ if for each vertex $v$, either (1) $v$ is link-complete and $v \in S$ or (2) $v$ is openly geodominated by some pair of vertices of $S$. The cardinality of a minimum open geodominating set in $G$ is the open geodomination number $og(G)$. We present sharp bounds for $g(G)$ and $og(G)$ in terms of the number of link-complete vertices in $G$. It is shown that for every pair $k$, $n$ of integers with $4 \leq k \leq n$, there exists a connected graph $G$ of order $n$ without link-complete vertices such that $og(G) = k$. %It is also shown %that there is no connected graph $G$ with $g(G) = 2$ and %$og(G)= 3$. It is also shown, for every nontrivial connected graph $G$, that $2 \leq g(G) \leq og(G) \leq 3 g(G)$. Furthermore, a pair $a$, $b$ of integers with $2 \leq a \leq b \leq 3a$ is realizable as the geodomination and open geodomination numbers of some nontrivial connected graph if and only if $(a, b) \neq (2, 3)$.