THE UPPER OPEN GEODETIC NUMBER OF A GRAPH

Abstract

For a connected graph G of order n, a set S of vertices of G is a geodetic set of G if each vertex v of G lies on a x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A set S of vertices of a connected graph G is an open geodetic set of G if for each vertex v in G, either v is an extreme vertex of G and v ∈ S; or v is an internal vertex of an x-y geodesic for some x,y∈S. An open geodetic set of minimum cardinality is a minimum open geodetic set and this cardinality is the open geodetic number, og(G). An open geodetic set S in a connected graph G is called a minimal open geodetic set if no proper subset of S is an open geodetic set of G. The upper open geodetic number og⁺(G) of G is the maximum cardinality of a minimal open geodetic set of G. It is shown that, for a connected graph G of order n, og(G)=n, if and only if og⁺(G)=n, and also that og(G)=3 if and only if og⁺(G)=3. It is shown that for positive integers a and b with 4 ≤ a ≤ b, there exists a connected graph G with og(G) =a and og⁺(G)=b. Also, it is shown that for positive integers a, b, c with 4 ≤ a ≤ b ≤ c and b ≤ 3a, there exists a connected graph G with g(G)=a, og(G)=b and og⁺(G)= c.