THE GEODETIC NUMBER OF A GRAPH

We introduce a new graph theoretic parameter, the geodetic number of a connected graph G = (V, E) as follows. The geodetic closure of a node set S subset-of V is the set of all nodes u is-an-element-of V which lie in some geodesic in G joining two nodes x and y of S. The geodetic number of a connected graph G, denoted by g(G), is the minimum number of nodes in a set S whose geodetic closure is all of V. We show that the determination of g(G) is an NP-hard problem and its decision prob lem is NP-complete, and present an algorithm for finding g(G).