On the Connected Geodetic Number of a Graph

Abstract

For a connected graph $G$ of order $p\ge 2$, a set $S\subseteq V(G)$ is a geodetic set of $G$ if each vertex $v\in V(G)$ lies on an $x$-$y$ geodesic for some elements $x$ and $y$ in $S$. The minimum cardinality of a geodetic set of $G$ is defined as the geodetic number of $G$, denoted by $g(G)$. A geodetic set of cardinality $g(G)$ is called a $g$-set of $G$. A connected geodetic set of $G$ is a geodetic set $S$ such that the subgraph $G[S]$ induced by $S$ is connected. The minimum cardinality of a connected geodetic set of $G$ is the connected geodetic number of $G$ and is denoted by $g_c(G)$. A connected geodetic set of cardinality $g_c(G)$ is called a $g_c$-set of $G$. Connected graphs of order $p$ with connected geodetic number $2$ or $p$ are characterized. It is shown that for positive integers $r,d$ and $n\ge d+1$ with $r\le d\le 2r$, there exists a connected graph $G$ of radius $r$, diameter $d$ and $g_c(G)=n$. Also, for integers $p,d$ and $n$ with $2\le d\le p-1$, $d+1\le n\le p$, there exists a connected graph $G$ of order $p$, diameter $d$ and $g_c(G)=n$.