An algorithm for prescribed multiple domination in arbitrary graphs

Let G = (V, E) be a graph with node set V, edge set E and V = n. A set S V is an open h-dominating set if every node vi V is adjacent to at least h nodes in S. Consider a vector P = [p1, p2, …, pn] with pi positive integers and pi ≤ deg(vi). A set S V is an open P-dominating set if every vi V is adjacent to at least pi nodes in S. We develop a backtracking algorithm that finds the open P-domination number of G, which is the smallest cardinality of an open P-dominating set. A comparative computational experiment is presented on arbitrary graphs of different sizes.