AbstractWe study the computational complexity of partitioning the vertices of a graph into generalized dominating sets. Generalized dominating sets are parameterized by two sets of nonnegative integers sigma and rho which constrain the neighborhood

N(v)of vertices. A setSof vertices of a graph is said to be a(sigma, rho)-set if forallvinS: |N(v)intersectS| insigmaand forallvnot inS: |N(v)intersectS| inrho. The (k,sigma, rho)-partition problem asks for the existence of a partition V_{1}, V_{2},...,V_{k}of vertices of a given graphGsuch that V_{i},i=1,2,...,kis a(sigma, rho)-set ofG. We study the computational complexity of this problem as the parameterssigma, rhoandkvary.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: graph partitioning, NP-completeness, complexity, domination

Selected references

- Ian Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718-720, November 1981.

- Daniel Leven and Zvi Galil. NP completeness of finding the chromatic index of regular graphs. Journal of Algorithms, 4(1):35-44, March 1983.

- Thomas J. Schaefer. The complexity of satisfiability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, pages 216-226, San Diego, California, 1-3 May 1978.

- Jan Arne Telle. Complexity of domination-type problems in graphs.
Nordic Journal of Computing, 1(1):157-171, Spring 1994.