ON THE EDGE-TO-VERTEX GEODETIC NUMBER OF A GRAPH

Let G = (V, E) be a connected graph with at least three vertices. For vertices u and v in G; the distance d(u, v) is the length of a shortest u-v path in G. A u-v path of length d(u, v) is called a u-v geodesic. For subsets A and B of V, the distance d(A, B), is defined as d(A, B) = min {d(x, y) : x is an element of A, y is an element of B}. A u-v path of length d(A, B) is called an A-B geodesic joining the sets A, B subset of V, where u is an element of A and v is an element of 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 subset of E is called an edge-to-vertex geodetic set 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 edge-to-vertex geodetic number g(ev)(G) of G is the minimum cardinality of its edge-to-vertex geodetic sets and any edge-to-vertex geodetic set of cardinality g(ev)(G) is an edge-to-vertex geodetic basis of G. Any edge-to-vertex geodetic basis is also called a g(ev)-set of G. It is shown that if G is a connected graph of size q and diameter d, then g(ev)(G) <= q - d + 2. It is proved that, for a tree T with q >= 2, g(ev)(T) = q - d + 2 if and only if T is a caterpillar. For positive integers r, d and l >= 2 with r <= d <= 2r, there exists a connected graph G with rad G = r, diam G = d and g(ev)(G) = l. Also graphs G for which g(ev)(G) = q, q - 1 or q - 2 are characterized.