Zbornik Radova Ekonomskog Fakulteta u Istočnom Sarajevu (Jan 2012)
THE UPPER OPEN GEODETIC NUMBER OF A GRAPH
Abstract
For a connected graph G of ordern, a set S of vertices of G is a geodetic set of G ifeach vertex n of G lies on a x-y geodesic for someelements x and y in S. The minimum cardinality of ageodetic set of G is defined as the geodetic numberof G, denoted by g(G). A geodetic set of cardinalityg(G) is called a g-set of G. A set S of vertices of aconnected graph G is an open geodetic set of G iffor each vertex n in G, either n is an extreme vertexof G and n Î S; or n is an internal vertex of an x-ygeodesic for some x,yÎS. An open geodetic set ofminimum cardinality is a minimum open geodeticset and this cardinality is the open geodeticnumber, og(G). An open geodetic set S in aconnected graph G is called a minimal opengeodetic set if no proper subset of S is an opengeodetic set of G. The upper open geodetic numberog+(G) of G is the maximum cardinality of aminimal open geodetic set of G. It is shown that, fora connected graph G of order n, og(G)=n, if andonly if og+(G)=n, and also that og(G)=3 if any onlyif og+(G)=3. It is shown that for positive integers aand b with 4 ≤ a ≤ b, there exists a connected graphG with og(G) =a and og+(G)=b. Also, it is shownthat for positive integers a, b, c with 4 ≤ a ≤ b ≤ cand b ≤ 3a, there exists a connected graph G withg(G)=a, og(G)=b and og+(G)= c.
