Computational Complexity of Geodetic Set
Mustafa Atıcı · International Journal of Computer Mathematics · 2002
For two vertices u and v of a graph G , the set H (u,v) consists of all vertices lying on some u m geodesic in G . If S is a set of vertices of G , then H(S) is the union of all sets H(u,v) for u,v ] S . If H(S) = V(G) , then S is a geodetic set for G . GEODETIC SET decision problem is defined and it is shown to be NP-Complete.