On characterizations of graphs having large geodetic numbers

Abstract

Let G be a nontrivial connected graph. For two vertices u and v of a graph G, the interval of u and v denoted by I(u, v) is the set containing all vertices lying on some u − v geodesic in G. Here a u − v geodesic is a path of length d(u, v). If S is a set of vertices of G, then I(S) is the union of all sets I(u, v) for vertices u and v in S. Now, if I(S) = V (G) then S is called a geodetic set of G and the geodetic number g(G) is the minimum cardinality among the geodetic sets of a graph G. In this research, we determine the geodetic number of complete multipartite graphs, wheels and cycles with one chord. Moreover, we characterize all connected graphs of order n having geodetic number n − 1. © SAS International Publications.