Point-Set Domination in Graphs. VIII: Perfect and Efficient PSD Sets

摘要

A perfect dominating set in a graph G is a dominating set D such that every vertex v in V - D is adjacent to a unique vertex u in D. An efficient dominating set is a perfect dominating set D which is independent as well. A point-set dominating set (or, psd-set, in short) is a dominating set D for which every subset S of V - D has a vertex u ∈ D such that the induced subgraph is connected. In this paper we determine necessary conditions for a graph to possess an efficient psd-set.