On the Vertex Geodomination Number of a Graph

Abstract

For a connected graph $G$ of order $p\ge 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\le n\le 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\le n\le 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\ge 2$ with $r\le d\le 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\le d\le p–1,1\le n\le p–1$ and $p–d–n+1\ge 0$, there exists a graph $G$ of order $p$, diameter $d$ and $g_x(G)=n$ for some vertex $x\in G$.