396ª Defesa de Dissertação de Mestrado - Independent locating-dominating sets in some graph classes

This dissertation explores the concept of Independent Locating-Dominating (ILD) sets in various graph classes, focusing on their structural properties, computational complexity, and algorithmic solutions. The work is divided into three main research articles, each addressing different aspects of the ILD problem. The first article investigates ILD sets in graphs constructed from cycles, such as power-of-cycle graphs, Möbius ladders, circular ladders, Jahangir graphs, helm graphs, and sunflower graphs. It is shown that power-of-cycle graphs do not admit ILD sets for any power k ≥ 2, while closed formulas for the ILD numbers of the other graph classes are derived, accompanied by constructive proofs.The second article focuses on P4-sparse graphs, a superclass of cographs, leveraging their modular decomposition properties to address the ILD problem. Necessary and sufficient conditions for the existence of ILD sets in P4-sparse graphs are established. Additionally, two algorithms are proposed: one for recognizing whether a P4-sparse graph admits an ILD set and another for computing an ILD set of minimum cardinality, both with a time complexity of O(n 2). The third article examines the computational complexity of ILD sets in restricted graph classes, proving that the problem remains N P-complete for bipartite
planar graphs with maximum degree five and for planar triangle-free subcubic graphs. The study also extends to Snarks, a subclass of cubic graphs, where exact formulas for the minimum size of ILD sets are provided for flower snarks and generalized Blanuša snarks. A fourth article was also developed, consisting of an extension of the results obtained in the previous articles to the Independent Identifying Codes (IIC) problem, which has a definition closely related to that of ILD.