Graphs with large total geodetic number
Hossein Ahangar Abdollahzadeh · Filomat · 2017
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 S. A set of vertices S V(G) is a total geodetic set if I[S] = V(G) and the subgraph G[S] induced by S has no isolated vertex. The total geodetic number, denoted by 1t(G), is the minimum cardinality among all total geodetic sets of G. In this paper, we characterize all connected graphs G of order n ≥ 3 with 1t(G)=n-1.