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