Generalized Domination in Special Graph Classes


We investigate the interplay of polynomial solvability and warranty of unique solvability of a problem under consideration, in the setting of generalized domination.

Given sets sigma and rho of nonnegative integers (as parameters of the problem), a set S of vertices of a graph is called (sigma,rho)-dominating if the number of S-neighbors of any vertex of S (of V-S) is an element of sigma (of rho, respectively). This notion was introduced by Telle and has been investaigated by Telle, Proskurowski, Heggernes, Miller, and others.


Subscribe to RSS - Colloquium