The geodetic number of the lexicographic product of graphs

AbstractA set S of vertices of a graph G is a geodetic set if every vertex of G lies in an interval between two vertices from S. The size of a minimum geodetic set in G is the geodetic number g(G) of G. We find that the geodetic number of the lexicographic product G∘H for a non-complete graph H lies between 2 and 3g(G). We characterize the graphs G and H for which g(G∘H)=2, as well as the lexicographic products T∘H that enjoy g(T∘H)=3g(G), when T is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph G, a formula that expresses the exact geodetic number of G∘H is established, where G is an arbitrary graph and H a non-complete graph