Edge geodetic number of a graph
A. P. Santhakumaran, J. John · Journal of Discrete Mathematical Sciences and Cryptography · 2007
For a non-trivial connected graph G, a set S⊆V(G) is called an edge geodetic cover of G if every edge of G is contained in a geodesic joining some pair of vertices in S. The edge geodetic number g 1 (G) of G is the minimum order of its edge geodetic covers and any edge geodetic cover of order g 1 (G) is an edge geodetic basis. Connected graphs of order p with edge geodetic number 2 are characterized. Various necessary conditions for the edge geodetic number of a graph to be p−1 and p are given. A geodetic graph of order p with edge geodetic number p is characterized. It is shown that every pair k, p of integers with 2≤k≤p is realizable as the edge geodetic number and order of some connected graph. For positive integers r, d and k≥2 with r<d≤2r, there exists a connected graph of radius r, diameter d and edge geodetic number k. It is shown that if G is a geodetic graph of order p and diameter d, then g1 (G)≤p−d+1. It is proved that, for a tree T, g 1 (T)=p−d+1 if and only if T is a caterpillar. Also, for integers p, d and k with 2≤d<p, 2≤k