The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p >= 2, a set S subset of V(G) is a geodetic set of G if each vertex v is an element of V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g(c)(G). A connected geodetic set of cardinality gc(G) is called a g(c)-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number g(c)(+)(G) is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for gc+(G) and determine the same for some special classes of graphs. For positive integers r,d and n >= d+1 with r <= d <= 2r, there exists a connected graph G with rad G = r, diam G = d and g(c)(+)(G) = n. Also, for any positive integers 2 <= a < b <= c, there exists a connected graph G such that g(G) = a, gc(G) = b and gc+(G) = c. A subset T of a gc-set S is called a forcing subset for S if S is the unique g(c)-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f(c)(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f(c)(G), is f(c)(G) = min{f(c)(S)}, where the minimum is taken over all g(c)-sets S in G. It is shown that for every pair a, b of integers with 0 <= a <= b - 4. there exists a connected graph G such that f(c)(G) = a and g(c)(G) = b. (C) 2008 Elsevier B.V. All rights reserved.