Graphs with Large Geodetic Number

Abstract

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 {\em geodetic set}  if $I[S]=V$. The {\em 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\ge 3$ 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\ge
2$, $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\ge 3$ with $g(G)=n-2$.