The Geo-Number of a Graph

Abstract

Let $G$ be a connected graph of order $p\ge 2$. The closed interval $I[x,y]$ consists of all vertices lying on some $x-y$ geodesic of $G$. If $S$ is a set of vertices of $G$, then $I[S]$ is the union of all sets $I\{x,y\}$ for $x,y\in S$. The geodetic number $g(G)$ is the minimum cardinality among the subsets $S$ of $V(G)$ with $I[S]=V$. A geodetic set of cardinality $g(G)$ is called a $g$-set of $G$. For any vertex $z$ in $G$, a set $S_x\subseteq V$ is an $x$-geodominating set of $G$ if each vertex $v\in V$ lies on an $z-y$ geodesic for some element $y$ in $S_z$. The minimum cardinality of an $x$-geodominating set of $G$ is defined as the $x$-geodomination number of $G$, denoted by $g_x(G)$ or simply $g_x$. An $x$-geodominating set $S_x$ of cardinality $g_x(G)$ is called a $g_x$-set of $G$. If $S_x\cup \{x\}$ is a $g$-set of $G$, then $x$ is called a geo-vertex of $G$. The set of all geo-vertices of $G$ is called the geo-set of $G$ and the number of geo-vertices of $G$ is called the geo-number of $G$ and it is denoted by $gn(G)$. For positive integers $r,d$ and $n\ge 2$ with $r<d\le 2r$, there exists a connected graph $G$ of radius $r$, diameter $d$ and $gn(G)=n$. Also, for each triple $p,d$ and $n$ with $3\le d\le p–1,2\le n\le p–2$ and $p–d–n+1\ge 0$, there exists a graph $G$ of order $p$, diameter $d$ and $gn(G)=n$. If the $x$-geodomination number $g_x(G)$ is same for every vertex $x$ in $G$, then $G$ is called a vertex geodomination regular graph or for short VGR-graph. If $S\cup \{x\}$ is same for every vertex $x$ in $G$, then $G$ is called a perfect vertex geodomination graph or for short PVG-graph. We characterize a PVG-graph.