On the Existence of Perfect (1, 2)-Dominating Sets in Graphs
Urszula Bednarz · Symmetry · 2025
In this paper, we investigate the existence of perfect (1,2)-dominating sets ((1,2)-PDS) in graphs with three vertices of maximum degree equal to n−2. A perfect (1,2)-dominating set is a special case of a (1,2)-dominating set. Graphs with such dominating sets may exhibit a symmetric structure. If a graph has at least one vertex of degree one, then it has a (1,2)-PDS. Hence, we consider only graphs with a minimum degree greater than or equal to 2. Therefore, a symmetric or asymmetric structure of graphs can be useful in determining whether a graph has a (1,2)-PDS. On the other hand, the symmetric or asymmetric structure may be even more helpful when studying the existence of (1,2)-PDS in relation to the maximum degree of a graph. Moreover, we analyze the structural conditions under which (1,2)-PDS exist, considering cases where the three vertices are adjacent or nonadjacent, and whether their neighborhoods are identical or distinct. Our study provides necessary and sufficient conditions for the existence of (1,2)-PDS in the given cases, extending the understanding of (1,2)-domination and its applications.