Graphs with Large Total 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 set of vertices $S \subseteq
V(G)$ is a {\it total geodetic set} if $I[S] = V(G)$ and the
subgraph $G[S]$ induced by $S$ has no isolated vertex. The {\em
total geodetic number}, denoted by $g_t(G)$, is the minimum
cardinality among all total geodetic sets of $G$. In this paper, we
characterize all connected
graphs $G$ of order $n\ge 3$ with $g_t(G)=n-1$.