Nearly perfect sets in graphs

✍ Scribed by Jean E. Dunbar; Frederick C. Harris Jr; Sandra M. Hedetniemi; Stephen T. Hedetniemi; Alice A. McRae; Renu C. Laskar

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 871 KB
• Volume: 138
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00205-w

✦ Synopsis

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 w {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 npIG) is NP-complete; we give a linear algorithm for determining rip(T) for any tree T; and we show that Np(G) can be calculated for any graph G in polynomial time.