The (a, b)-forcing geodetic graphs

For every pair of vertices u, v in a graph a u-v geodesic is a shortest path from u to v. For a graph G, let IG |u,v| denote the set of all vertices lying on a u-v geodesic, and for S subset of V(G), let Ig|S| denote the union of all IG|u,v| for all u,v is an element of S. A set S subset of V(G) is a geodetic set if IG |S| = V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F subset of V(G) is called a forcing subset of G if there exists a unique minimum geodetic set containing F. A forcing subset F is critical if every proper subset of F is not a forcing subset. The cardinality of a minimum critical forcing subset in G is called the forcing geodetic number f(G) of G and the cardinality of a maximum critical forcing subset in G is called the upper forcing geodetic number f(+) (G) of G. If G is a graph with F(G) = 0, then G has a unique minimum geodetic set; that is, F(+) (G) = 0. In the paper, we prove that, for any nonnegative integers a, b and c with 1 <= a <= b <= C -2 or 4 <= a + 2 <= b <= c, there exists a conected graph G with f(G) = a, f(+) (G) = b, and g(G) = c. This result solves a problem of Zhang [P. Zhang, The upper forcing geodetic number of a graph, Ars Combin, 62 (2002) 3-15]. (C) 2009 Published by Elsevier B.V.