Minimal Restrained Domination Algorithms on Trees Using Dynamic Programming

ASU Author/Contributor (non-ASU co-authors, if there are any, appear on document)
Jeremy Booker (Creator)
Appalachian State University (ASU )
Web Site:
Alice McRae

Abstract: In this paper we study a special case of graph domination, namely minimal restrained dominating sets on trees. A set S ? V is a dominating set if for every vertex u ? V-S, there exists v ? S such that uv ? E. A set S ? V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and another vertex in V-S. A restrained dominating set S is a minimal restrained dominating set if no proper subset of S is also a restrained dominating set. We give a dynamic programming style algorithm for generating largest minimal restrained dominating sets for trees and show that the decision problem for minimal restrained dominating sets is NP-complete for general graphs. We also consider independent restrained domination on trees and its associated decision problem for general graphs.

Additional Information

Booker, J. (2013). Minimal Restrained Domination Algorithms on Trees Using Dynamic Programming. Unpublished master’s thesis. Appalachian State University, Boone, NC.
Language: English
Date: 2013
Graph domination, Restrained dominating sets on trees, Independent restrained dominating sets on trees , Minimal restrained dominating sets

Email this document to