New polynomial circular-arc instances of tuple domination in graphs

ESCALANTE, MARIANA SILVINA; LEONI, VALERIA ALEJANDRA; LOPEZ PUJATO, MARIA INES

Viña del Mar

Conferencia; APPLIED COMBINATORIAL OPTIMIZATION 2021-2022; 2022

ALIO EURO

It is well-known that 1-tuple domination (classical domination) is NP-hard for general graphs. For circular-arc graphs, it is efficiently solvable due to M.S. Chang (1998). On the other side, efficient algorithms of a known generalization ?𝑘-tuple domination (𝑘 fixed)? of 1-tuple domination are not developed for circular-arc graphs and 𝑘 greater than 2. In this work, we introduce a new circular-arc graph subclass. For this subclass, we present a lower bound for the 𝑘-tuple domination number for every positive integer 𝑘. Finally, we find the exact value of these numbers by proving how to achieve this bound.