The closed geodetic numbers of graphs
Abstract
Study on the closed geodetic number evolved from two classes of graphical games called achievement and avoidance games [10]. Let G = (V(G], E(G]] be a connected graph. For S ⊆ V (G), the geodetic closure IG [S] of S is the set of all vertices on geodesics (shortest paths) between two vertices of S. We select vertices of G sequentially as follows: Select a vertex v 1 and let S1 = {v1}. Select a vertex V 2 ≠ v1 and let S2 = {v1, v 2}. Then successively select vertex vi ∉ I G[Si-1] and let Si = {v1, v 2,...,vi}. Since the set V(G) is finite, there is a k for which IG[Sk] = V(G). We define the closed geodetic number of G, denoted cgn(G), to be the smallest k for which the selection of v k in the given manner makes IG[Sk] = V(G]. In [2], the closed geodetic number cgn(G] of a connected graph G is introduced very briefly. This graphical invariant is closely related to the geodetic number gn of a graph. In fact, gn(G] = 2 if and only if cgn(G] = 2 and gn(G] = 3 if and only if cgn(G) = 3. However in general, we can only have gn(G] ≤ cgn(G). In this paper, we characterize connected graphs G of order p for which cgn(G] = p, p - 1, 2 or 3. For any positive integers k and n for which 4 ≤ k ≤ [n/2], there always exists a connected graph G where |V(G)| = n, gn(G] = 4 and cgn(G] = k. And for integers n,m and k with 5 ≤ m ≤ k and 2k - m + 4 ≤ n, there exists a (connected) graph G such that [V(G)| = n, gn(G] = m and cgn(G) = k. We also determine the closed geodetic numbers of the joins of more general graphs.
