Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes In this paper, we study the computational complexity of finding the geodetic number of graphs. A set of vertices S of a graph G is a geodetic set if any vertex of G lies in some shortest path between some pair of vertices from S. The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality. In this paper, we prove that solving MGS is NPhard on planar graphs with a maximum degree six and line graphs. We also show that unless (PNP), there is no polynomial time algorithm to solve MGS with sublogarithmic approximation factor (in terms of the number of vertices) even on graphs with diameter 2. On the positive side, we give an (Oleft( root 3 of nlog nright) )approximation algorithm for MGS on general graphs of order n. We also give a 3approximation algorithm for MGS on solid grid graphs which are planar.

On the Geodetic and Hull Numbers of Shadow Graphs. Given two vertices u, v in a graph G, a shortest (u, v)path in G is called an (u, v)geodesic. Let (I_Gu, v) denote the set of all vertices in G lying on some (u, v)geodesic. Given a set (Tsubseteq V(G)), let (I_GTcup _u,v in TI_Gu, v). If (I_GTT), we call T a convex set. The convex hull, denoted by (langle T rangle _G), is the smallest convex set containing T. A subset T of vertices of a graph G is a hull set if (langle T rangle _GV(G)). Moreover, T is a geodetic if (I_GTV(G)). The hull number h(G) of a graph G is the minimum size of a hull set. The geodetic number g(G) of G is the minimum size of a geodetic set. The shadow graph, denoted by S(G), of a graph G is the graph obtained from G by adding a new vertex (vprime ) for each vertex v of G and joining (vu0027) to the neighbors of v in G. In this paper, we study the geodetic and hull numbers of shadow graphs. Bounds for the geodetic and hull numbers of shadow graphs are obtained and for several classes exact values are determined. Graphs G for which (g(S(G))in 2, 3) are characterized.