Advances and Applications in Discrete Mathematics
Volume 26, Issue 1, Pages 83 - 108
(January 2021) http://dx.doi.org/10.17654/DM026010083 |
|
ON GRAPHS WITH PAIRWISE DISJOINT EFFICIENT DOMINATING SETS AND EFFICIENT DOMINATION IN TREES IN TERMS OF SUPPORT VERTICES
A. Senthil Thilak, Sujatha V. Shet and S. S. Kamath
|
Abstract: A set S of vertices of a graph G is an efficient dominating set (EDS) if it is a dominating set satisfying the condition for all That is, S is an EDS of G if each vertex in is dominated exactly once by S. A graph G is efficiently dominatable if it has an EDS. The class of efficiently dominatable graphs is denoted by In this paper, some improved bounds on domination number of efficiently dominatable graphs are obtained. We study the structural properties of graphs possessing pairwise disjoint efficient dominating (PWDED) sets and characterize such graphs. This study of PWDED sets is significant in the study of critical concepts in efficient domination and also has its applications in the analysis of fault tolerant networks. As an attempt to characterize the efficiently dominatable trees, we identify certain necessary/sufficient conditions for a tree to be efficiently dominatable. The vertices in a tree are classified into three categories, with support vertices as one among the three. The results are obtained based on the existence and the nature of support vertices. Also, we characterize and discuss the properties of efficiently dominatable trees of diameter up to five. |
Keywords and phrases: efficient domination, efficient domination number, 2-packing, independent perfect domination, efficiently dominatable trees, support vertices.
|
|
Number of Downloads: 157 | Number of Views: 467 |
|