Graphs With Large Geodetic Number

Hossein Abdollahzadeh Ahangar, Saeed Kosari, Seyed Mahmoud Sheikholeslami, Lutz Volkmann

For two vertices $u$ and $v$ of a graph $G$, the set $I[u,v]$ consists of all vertices lying on some $u-v$ geodesic in $G$. If $S$ is a set of vertices of $G$, then $I[S]$ is the union of all sets $I[u,v]$ for $u,v\in S$. A subset $S$ of vertices of $G$ is a \emph{geodetic set} if $I[S]=V$. The \emph{geodetic number} $g(G)$ is the minimum cardinality of a geodetic set of $G$. It was shown that a connected graph $G$ of order $n\geq3$ has geodetic number $n-1$ if and only if $G$ is the join of $K_1$ and pairwise disjoint complete graphs $K_{n_1},K_{n_2} ,\ldots,K_{n_r}$, that is, $G=(K_{n_1}\cup K_{n_2}\cup\ldots K_{n_r})+K_1$, where $r\geq2$, $n_1,n_2,\ldots n_r$ are positive integers with $n_1+n_2+\ldots+n_r=n-1$. In this paper we characterize all connected graphs $G$ of order $n\geq3$ with $g(G)=n-2$.