DIMACS TR: 2006-22

Domination in Graphs of Low Degree



Authors: Vadim Lozin and Martin Milanic

ABSTRACT

We study the computational complexity of the dominating set problem on graphs of bounded vertex degree. In general, this problem is NP-hard. However, under certain restrictions it becomes polynomial-time solvable. In this paper we identify two graph parameters to which the complexity of the problem is sensible.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-22.ps.gz
DIMACS Home Page