Given two vertices u and v of a connected graph G, the closed interval I-G[u, v] is the set of all vertices lying in some u-v geodesic in G. If S subset of V(G), then I-G[S] = boolean OR{I-G[u,v] : u,v is an element of S}. A set S of vertices in G is called a geodetic cover of G if I-G[S] = V(G). The geodetic number gn(G) of G is the minimum cardinality of a geodetic cover of G. A geodetic cover of smallest cardinality is called a geodetic basis of G. Suppose that in constructing a geodetic cover of G, we select a vertex v(1) and let S-1 = {v(1)}. Select a vertex v(2) not equal v(1) and let S-2 = {v(1),v(2)). Then successively select vertex v(i) is not an element of I-G[Si-1] and let S-i = {v(1), v(2), ... ,v(i)}. The closed geodetic number cgn(G) and the upper closed geodetic number ucgn(G) of G is the smallest and the largest k, respectively, for which selection of v(k) in the given manner makes I-G[S-k] = V(G). A closed geodetic cover S of G is a minimal closed geodetic cover of G if no proper subset of S is a closed geodetic cover of G. The minimal closed geodetic number mcgn(G) is the maximum cardinality of a minimal closed geodetic cover of G. In this paper, it is shown that ucgn(G) = mcqn(G) if and only if G is complete, while cgn(G) and mcgn(G) coincide among extreme geodesic graphs G. Moreover, for complete bipartite graphs K-m,K-n, cgn(K-m,K-n) = mcgn(K-m,K-n) if and only if m = n. More interesting, for every triple a, b, c is an element of Z(+), with 2 <= a < b < c, a, b, and c are realizable as closed geodetic number, minimal closed geodetic number, and upper closed geodetic number, respectively, of a connected graph. We also determine here the minimal closed geodetic numbers of graphs resulting from the join of graphs.
展开▼
