pipette
ESEspañol

On -limited domination: complexity and Sierpi\'nski graphs

Dragana Bo\v{z}ovi\'{c}

Preprint

In the authors' words

A dominating set of a graph is called -limited if every vertex of has at most neighbors outside . The minimum cardinality among all -limited dominating sets of is the -limited domination number, denoted by . In this paper, we prove that the -Limited Dominating Set problem is -complete, answering an open question posed in the literature. We further show that, for every positive integer , the -Limited Dominating Set problem is -complete even when restricted to planar graphs. In addition, we study the -limited domination number of Sierpi\'nski graphs. We determine the exact value of for all integers and , and obtain the -limited domination number for the planar family .

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.