Edge Geodetic Domination Number of a Graph

Abstract

In this paper the concept of edge geodetic domination number of a graph is introduced. A set of vertices S of a graph is an edge geodetic domination set (EGD) if it is both edge geodetic set and a domination set of G. The edge geodetic domination number (EGD number) of G, $\gamma$g_{e}$(G) is the cardinality of a minimum EGD set. EGD numbers of some connected graphs are realized. Connected graphs of order p with EGD number p are characterized. It is shown that for any two integers p and q such that $2 \le p \le  q$, there exist a connected graph G with $\gamma g(G) = p $ and $\gamma g_{e}(G) = q$. Also it is shown that there is a connected graph G such that $\gamma(G) = p$, $g_{e}(G) = q$ and $\gamma g_{e} (G) = p + q$.