On the Vertex Geodomination Number of a Graph

Abstract

For a connected graph \(G\) of order \(p \geq 2\), a set \(S \subseteq V(G)\) is an \(x\)-geodominating set of \(G\) if each vertex \(v \in V(G)\) lies on an \(x\)-geodesic for some element \(y \in S\). The minimum cardinality of an \(x\)-geodominating set of \(G\) is defined as the \(\alpha\)-geodomination number of \(G\), denoted by \(g_x(G)\) or simply \(g_x(G)\). An \(x\)-geodominating set of cardinality \(g_x(G)\) is called a \(g_x(G)\)-set. A connected graph of order \(p\) with vertex geodomination numbers either \(p – 1\) or \(p – 2\) for every vertex is characterized. It is shown that there is no graph of order \(p\) with vertex geodomination number \(p – 2\) for every vertex. Also, for an even number \(p\) and an odd number \(n\) with \(1 \leq n \leq p – 1\), there exists a connected graph \(G\) of order \(p\) and \(g_x(G) = n\) for every vertex \(x \in G\), and for an odd number \(p\) and an even number \(n\) with \(1 \leq n \leq p – 1\), there exists a connected graph \(G\) of order \(p\) and \(g_x(G) = n\) for every vertex \(x \in G\). It is shown that for any integer \(n > 2\), there exists a connected regular as well as a non-regular graph \(G\) with \(g_x(G) = n\) for every vertex \(x \in G\). For positive integers \(r, d\) and \(n \geq 2\) with \(r \leq d \leq 2r\), there exists a connected graph \(G\) of radius \(r\), diameter \(d\) and \(g_x(G) = n\) for every vertex \(x \in G\). Also, for integers \(p, d\) and \(n\) with \(3 \leq d \leq p – 1, 1 \leq n \leq p – 1\) and \(p – d – n + 1 \geq 0\), there exists a graph \(G\) of order \(p\), diameter \(d\) and \(g_x(G) = n\) for some vertex \(x \in G\).