The (a,b)-forcing geodetic graphs

AbstractFor 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⊆V(G), let IG[S] denote the union of all IG[u,v] for all u,v∈S. A set S⊆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⊆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 connected 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]