Indian Journal of Science and Technology

Abstract

For any two vertices u and v of a graph G = (V, E), any shortest path joining u and v is called a u-v geodesic. Closed interval I[u,v] of u and v is the set of those vertices belonging to at least one u-v geodesic. A subset S of V(G) is an geodetic set if every vertex of G lies in at least one closed interval between the vertices of S. The geodetic set of a minimum cardinality in G is called as minimum geodetic set. The cardinality of the minimum geodetic set is the geodetic number of G denoted by gn(G). For a non-trivial connected graph G, a set S ofV (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 egn (G) of G is the minimum order of its edge geodetic covers and any edge geodetic cover of order egn(G)is an edge geodetic basis. This paper introduces the algorithms to find geodetic numbers and edge geodetic numbers in connected graphs using dynamic programming approach.

Keywords: Diameter, Distance, Eccentricity, Edge Geodetic Cover, Edge Geodetic Number, Geodesic, Geodetic Number, Geodetic Set, Radius