Edge Geodetic Dominating Sets of Some Graphs

Abstract

Let $G$ be a simple graph. A subset $D$ of vertices in $G$ is a dominating set of $G$ if every vertex not in $D$ has at least one neighbor in $D$. The domination number $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. An edge geodetic set of $G$ is a set $S \subseteq V(G)$ such that every edge of $G$ is contained in a geodetic joining some pair of vertices in $S$. The edge geodetic number $g_e(G)$ of $G$ is the minimum cardinality of edge geodetic set. A set of vertices $S$ in $G$ is an edge geodetic dominating set of $G$ if $S$ is both an edge geodetic set and a dominating set. The minimum cardinality of an edge geodetic dominating set of $G$ is its edge geodetic domination number and is denoted by $\gamma_{g_e}(G)$. In this study, we determined the edge geodetic domination number of graphs obtained through the deletion of independent edges of complete graphs and graphs resulting from the $K_r$-gluing of complete graphs. It is also shown that for any positive integers $2 \leq a \leq b$, there exists a connected graph $G$ such that $g_e(G)=a$ and $\gamma_{g_e}(G)=b$.