Location-Domination Type Problems Under the Mycielski Construction

Publications

Location-Domination Type Problems Under the Mycielski Construction

Year : 2024

Publisher : Springer Science and Business Media Deutschland GmbH

Source Title : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Document Type :

Abstract

We consider the following variants of the classical minimum dominating set problem in graphs: locating-dominating set, locating total-dominating set and open locating-dominating set. All these problems are known to be hard for general graphs. A typical line of attack, therefore, is to either determine the minimum cardinalities of such sets in general or to establish bounds on these minimum cardinalities in special graph classes. In this paper, we study the minimum cardinalities of these variants of the dominating set under a graph operation defined by Mycielski in [21] and is called the Mycielski construction. We provide some general lower and upper bounds on the minimum sizes of the studied sets under the Mycielski construction. We apply the Mycielski construction to stars, paths and cycles in particular, and provide lower and upper bounds on the minimum cardinalities of such sets in these graph classes. Our results either improve or attain the general known upper bounds.