Changing and unchanging efficient domination in graphs with respect to edge addition

Abstract

A dominating set $S $ of a graph $ G $ is an \textit{efficient dominating set} (EDS) of $G$ if $|N_G[v]\cap S|=1$, for all $v\in V(G)$. $G$ is \textit{efficiently dominatable} or \textit{efficient} if it has an EDS. Not all graphs are efficient. The class of efficient graphs is denoted by $\mathscr{E}$. If $G\in \mathscr{E}$, then any EDS of $G$ has its cardinality equal to the domination number of $G$, denoted by $\gamma(G)$. An edge $e\in E(\overline{G})$ is \textit{critical} or $\gamma$-\textit{critical} if $\gamma(G+e)\ne \gamma(G)$. The study of critical concepts exists for domination and its variants. We extend this study to graphs which are efficient. This paper deals with the study of the properties of critical edges of graphs in $ \mathscr{E} $. Depending on whether the addition of an edge increases or decreases or leaves unaltered $\gamma(G)$, the edge set of $ G $ is classified respectively into three sets: $EA^+$, $EA^-$, $EA^0$. To study the changing and unchanging property of efficient domination, we define the classes $UEA_{E}=UEA \cap \mathscr{G}_{+e}$, $CEA_{E}=CEA \cap \mathscr{G}_{+e}$, where $\mathscr{G}_{+e}=\{G: G\in \mathscr{E}$ and $G+e\in \mathscr{E}$, for all $e\in E(\overline{G})$\}, $ UEA=\{G: \gamma(G)=\gamma(G+e)$, for all $e\in E(\overline{G})\} $ and $ CEA=\{G: \gamma(G)\ne\gamma(G+e)$, for all $e\in E(\overline{G})\} $. We characterize the critical edges, edge critical sets, the two classes of graphs defined above and identify their relationship with critical vertices of those graphs in $\mathscr{E}$. We also identify the relationship between all classes of graphs resulting from vertex criticality (vertex removal) and edge criticality (edge removal and edge addition) and represent through Venn diagram. This study plays a significant role in the analysis and design of fault tolerant networks.