Extreme geodesic graphs

For two vertices u and v of a graph G, the closed interval 1[u, v] consists of u, v, and all vertices lying in some u-v geodesic of G, while for S C V(G), the set I[S] is the union of all sets I[u, v] for u,v is an element of S. A set S of vertices of G for which I[S] = V(G) is a geodetic set for G, and the minimum cardinality of a geodetic set is the geodetic number g(G). A vertex v in G is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in G is its extreme order ex(G). A graph G is an extreme geodesic graph if g(G) = ex(G), that is, if every vertex lies on a. u-v geodesic for some pair u, v of extreme vertices. It is shown that every-pair a, b of integers with 0 less than or equal to alpha less than or equal to b is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers r, d, and k greater than or equal to 2, it is shown that there exists an extreme geodesic graph G of radius r, diameter d, and geodetic number k. Also, for integers n, d, and k with 2 < d < n, 2 less than or equal to k less than or equal to n, and n - d - k + 1 greater than or equal to 0, there exists a connected extreme geodesic graph G of order n, diameter d, and geodetic number k. We show that every graph of order n with geodetic number n - 1 is an extreme geodesic graph. On the other hand, for every pair k, n of integers with 2 < k < n - 2, there exists a connected graph of order n with geodetic number k that is not an extreme geodesic graph.