$k$-Geodomination in Graphs

Abstract

For an integer $k\ge 1$, a vertex $v$ of a graph $G$ is $k$-geodominated by a pair $z,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\ne 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 $o{g}_k(G)$.

It is shown that each triple $a,b,k$ of integers with $2\le a\le b$ and $k\ge 2$ is realizable as the geodomination number and $k$-geodomination number of some tree. For each integer $k\ge 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 if $2\le a=n$ or $2\le a\le 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 $l$ $k$-extreme vertices, then $\{2,l\}\le g_k(G)\le o{g}_k(G)\le 3g_k(G)–2l$ for every integer $k$ with $2\le k\le d$.