The minimal closed geodetic numbers of graphs

Abstract

Given two vertices u and υ of a connected graph G., the closed interval J _G[u, υ] is the set of all vertices lying in some u-υ geodesic in Q. If S ⊆ V(G), then I _G[S] = ∪{I _G[u,υ]: u,υ ∈ 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 υ ₁ and let S ₁ = {υ ₁}. Select a vertex υ ₂ ≠ υ ₁ and let S ₂ = {υ ₁, υ ₂}. Then successively select vertex υ ₁ ∉ I _G[S _i-1] and let S _i = {υ ₁, υ ₂,υ _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 υ _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) = mcgn(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,n cgn(K _m,n) = mcgn(K _m,n) if and only if m = n. More interesting, for every triple a, 6, c ∈ 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.