• THE UPPER EDGE-TO-VERTEX GEODETIC NUMBER OF A GRAPH

Abstract

Let G be a non-trivial connected graph with at least three vertices. For subsets A and B of V(G), the distance d(A, B) is defined as d(A, B) = min{d(x, y) : xA, yB}. A u  v path of length d(A, B) is called an A  B geodesic joining the sets A, B  V(G), where u  A and v  B. A vertex x is said to lie on an A  B geodesic if x is a vertex of an A  B geodesic. A set S  E is called an edge-to-vertex geodetic set of G if every vertex of G is either incident with an edge of S or lies on a geodesic joining a pair of edges of S. The minimum cardinality of an edge-to-vertex geodetic set of G is gev(G). Any edge-to-vertex geodetic set of cardinality gev(G) is called an edge-to-vertex geodetic basis of G. An edge-to-vertex geodetic set S in a connected graph G is called a minimal edge-to-vertex geodetic set if no proper subset of S is an edge-to-vertex geodetic set of G. The upper edge-to-vertex geodetic number gev+(G) of G is the maximum cardinality of a minimal edge-to-vertex geodetic set of G. Some general properties satisfied by this concept are studied. For a connected graph G of size q with upper edge-to-vertex geodetic number q or q – 1 are characterized. It is shown that for every two positive integers a and b, where 2 ≤ a ≤ b, there exists a connected graph G with gev(G) = a and gev+(G) = b.