MMN-353
On the edge-to-vertex geodetic number of a graph
Abstract
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 ∈ A, y ∈ B}. A u − v path of length d(A,B) is
called an A − B geodesic joining the sets A,B ⊆ V, 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 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 gev(G) of G is the minimum cardinality of its edge-to-vertex geodetic sets and
any edge-to-vertex geodetic set of cardinality gev(G) is an edge-to-vertex geodetic basis
of G. Any edge-to-vertex geodetic basis is also called a gev-set of G. It is shown that if
G is a connected graph of size q and diameter d, then gev(G) ≤ q − d + 2. It is proved
that, for a tree T with q ≥ 2, gev(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 gev(G) = l. Also graphs G for which gev(G) = q, q − 1 or
q − 2 are characterized.
Vol. 13 (2012), No. 1, pp. 107-119