The total 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 u - v 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 ∈ 5. A set of vertices S ⊆ V(G) is a geodetic set if I[S] = V(G), and the minimum cardinality of a geodetic set is the geodetic number g(G). A geodetic set S ⊆ V(G) is a total geodetic set if the subgraph G[S] induced by S has no isolated vertices. The minimum cardinality of a total geodetic set is the total geodetic number gt(G). A subset T of a minimum total geodetic set 5 is called a forcing subset for S if S is the unique minimum total geodetic set containing T. The forcing total geodetic number of S is the minimum cardinality among the forcing subsets of 5, and the forcing total geodetic number f(G,gt) of G is the minimum forcing total geodetic number among all minimum total geodetic sets of G. We determine sharp bounds for gt(G) and f(G,gt). The minimum cardinality of a geodetic set which induces a connected graph is the connected geodetic number gc(G). We present necessary and sufficient conditions which determine for every triple of integers a, b, c whether there exists a nontrivial connected graph G with: (i) a = g(G), b = gt(G), c = |V(G)|; (ii) a = rad G, b = diam G, c = gt(G); (iii) a = gt(G), b = gc(G), c = |V(G)|. We find all ordered pairs (a, 6) of integers which are realizable as the forcing total geodetic number and total geodetic number for some nontrivial connected graph, respectively.
