On the geodetic and geodetic domination numbers of a graph

A subset SS of vertices in a graph GG is a called a geodetic set   if every vertex not in SS lies on a shortest path between two vertices from SS. A subset DD of vertices in GG is called dominating   if every vertex not in DD has at least one neighbor in DD. A geodetic dominating set  SS is both a geodetic and a dominating set. The geodetic (domination, geodetic domination) number  g(G)g(G) (γ(G)γ(G), γg(G)γg(G)) of GG is the minimum cardinality among all geodetic (dominating, geodetic dominating) sets in GG. In this paper, we study both concepts of geodetic and geodetic dominating sets and derive some upper bounds on the geodetic and the geodetic domination numbers. In particular, we show that if GG has minimum degree at least 2 and girth at least 6, then γg(G)=γ(G)γg(G)=γ(G). We also show that the problem of finding a minimum geodetic dominating set is NP-hard even for chordal or chordal bipartite graphs. Moreover, we present some Nordhaus–Gaddum-type results and study the geodetic and geodetic domination numbers of block graphs.