Nearly perfect sets in graphs Original Research Article

In a graph G=(V, E), a set of vertices S is nearly perfect if every vertex in V-S is adjacent to at most one vertex in S. Nearly perfect sets are closely related to 2-packings of graphs, strongly stable sets, dominating sets and efficient dominating sets. We say a nearly perfect set S is 1-minimal if for every vertex u in S, the set S-u is not nearly perfect. Similarly, a nearly perfect set S is 1-maximal if for every vertex u in V-S, S ∪ u is not a nearly perfect set. Lastly, we define np(G) to be the minimum cardinality of a 1-maximal nearly perfect set, and Np(G) to be the maximum cardinality of a 1-minimal nearly perfect set. In this paper we calculate these parameters for some classes of graphs. We show that the decision problem for np(G) is NP-complete; we give a linear algorithm for determining np(T) for any tree T; and we show that Np(G) can be calculated for any graph G in polynomial time.