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

Abstract

A dominating set S of a graph g is an efficient dominating set (EDS) of g if Ng[v]?S=1, for all v e V(g). g is efficiently dominatable or efficient if it has an EDS. Not all graphs are efficient. The class of efficient graphs is denoted by E. If g e E, then any EDS of g has its cardinality equal to the domination number of g, denoted by g(g). An edg+e e e E(g) is critical or g-critical if y(g+e) ? y(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 edg+es of graphs in E. Depending on whether the addition of an edg+e increases or decreases or leaves unaltered g(g), the edg+e set of g is classified respectively into three sets: EA+, EA-, EA0. To study the changing and unchanging property of efficient domination, we define the classes UEAE = UEA? <inf>g+e</inf>, CEAE = CEA?<inf>g+e</inf>, where g+e = {g: g ? E and <inf>g+e</inf> ? E, for all e ? E(g)g, UEA = (g: g(g) = g(g+e), for all e ? E(g)g and CEA = (g: g(g) ? g(g+e), for all e ? E(g)g. We characterize the critical edg+es, edg+e critical sets, the two classes of graphs defined above and identify their relationship with critical vertices of those graphs in E. We also identify the relationship between all classes of graphs resulting from vertex criticality (vertex removal) and edg+e criticality (edg+e removal and edg+e addition) and represent through Venn diagram. This study plays a significant role in the analysis and design of fault tolerant networks. © 2020 by the authors.