pipette
ESEspañol

On -limited and -domination in cubic graphs

Goran Radi\'c, Aleksandra Tepeh

Preprint

In the authors' words

A dominating set of a graph is called -limited if every vertex of has at most one neighbor outside , while a -dominating set is a dominating set in which every vertex of the set has at least two neighbors within the set. These two notions coincide on cubic graphs. We prove that the decision problem 1-Limited Dominating Set is -complete even when restricted to -connected planar cubic graphs, thereby completing the known complexity results for -Limited Dominating Set for all fixed positive integers . We also determine the exact -limited domination number of the entire Goldberg family. This provides a further infinite family of cubic graphs supporting several open conjectures and proposed bounds concerning -domination and induced cycles.

Main resultThe abstract does not state a limitation.

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