On the geodetic number of a graph

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 ∈ S . The geodetic number g ( G ) is the minimum cardinality among the subsets S of V ( G ) with I ( S ) = V ( G ). It is shown that if G is a graph of order n and diameter d then g ( G ) ≤ n − d + 1 and this bound is sharp. For positive integers r , d , and k ≥ 2 with r ≤ d ≤ 2 r , there exists a connected graph G of radius r , diameter d , and g ( G ) = k . Also, for integers n , d , and k with 2 ≤ d < n , 2 ≤ k < n , and n − d − k + 1 ≥ 0, there exists a graph G of order n , diameter d , and g ( G ) = k . It is shown, for every nontrivial connected graph G , that g ( G ) ≤ g ( G × K 2 ). A sufficient condition for the equality of g ( G ) and g ( G × K 2 ) is presented. A graph F is a minimum geodetic subgraph if there exists a graph G containing F as an induced subgraph such that V ( F ) is a minimum geodetic set for G . Minimum geodetic subgraphs are characterized. © 2002 John Wiley & Sons, Inc.