\(k\)-Geodomination in Graphs

Abstract

For an integer \(k \geq 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 \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 if \(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 \(l\) \(k\)-extreme vertices, then \(\{2, l\} \leq g_k(G) \leq og_k(G) \leq {3}g_k(G) – 2l\) for every integer \(k\) with \(2 \leq k \leq d\).