The forcing 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 uv 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. A set S is a geodetic set if I(S) = V (G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T . The forcing geodetic number f G (S) of S is the minimum cardinality among the forcing subsets of S, and the forcing geodetic number f (G) of G is the minimum forcing geodetic number among all minimum geodetic sets of G. The forcing geodetic numbers of several classes of graphs are determined. For every graph G, f (G) g(G). It is shown that for all integers a, b with 0 a b, a connected graph G such that f (G) = a and g(G) = b exists if and only if (a, b) / {(1, 1), (2, 2)}.