k-Geodomination in graphs



For an integer $k \geq 1$, a vertex $v$ of a graph $G$ is $k$-geodominated by a pair $x, y$ of vertices in $G$ if $d(x, y) = k$ and $v$ lies on an $x-y$ geodesic of $G$. A set $S$ of vertices of $G$ is a $k$-geodominating set if each vertex $v$ in $V - S$ is $k$-geodominated by some pair of distinct vertices of $S$. The minimum cardinality of a $k$-geodominating set of $G$ is its $k$-geodomination number $g_k(G)$. A vertex $v$ is openly $k$-geodominated by a pair $x, y$ of distinct vertices in $G$ if $v$ is $k$-geodominated by $x$ and $y$ and $v \neq x, y$. A vertex $v$ in $G$ is a $k$-extreme vertex if $v$ is not openly $k$-geodominated by any pair of vertices in $G$. A set $S$ of vertices of $G$ is an open $k$-geodominating set of $G$ if for each vertex $v$ of $G$, either (1) $v$ is $k$-extreme and $v \in S$ or (2) $v$ is openly $k$-geodominated by some pair of distinct vertices of $S$. The minimum cardinality of an open $k$-geodominating set in $G$ is its open $k$-geodomination number $og_k(G)$. It is shown that each triple $a$, $b$, $k$ of integers with $2 \leq a \leq b$ and $k \geq 2$ is realizable as the geodomination number and $k$-geodomination number of some tree. For each integer $k \geq 1$, we show that a pair $(a, n)$ of integers is realizable as the $k$-geodomination number (open $k$-geodomination number) and order of some nontrivial connected graph if and only of $2 \leq a = n$ or $2 \leq a \leq n-k+1$. We investigate how $k$-geodomination numbers are affected by adding a vertex. We show that if $G$ is a nontrivial connected graph of diameter $d$ with exactly $\ell$ $k$-extreme vertices, then $\max \ \{2, \ell\} \leq g_k(G) \leq og_k (G) \leq 3g_k(G) - 2\ell$ for every integer $k$ with $2 \leq k \leq d$.