Independent locating-dominating sets in P4-sparse graphs - Lemos, Dayllon Vinícius Xavier; Cappelle, Márcia Rodrigues; Coelho, Erika Morais Martins; Foulds, Leslie Richard; Longo, Humberto José (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da Computação, 2025)
A vertex subset S of a graph of order n is termed independent locating-dominating (an ILD set for short) if it is independent, dominating and no two distinct vertices of V (G) \ S have the same open neighbourhood in S, i.e. N G (u)∩S ≠ N G (v)∩S, ∀ u, v ∈ V (G)\S, u≠ v. We study ILD sets in P 4 -sparse graphs and propose two algorithms: one for recognizing whether or not a graph admits an ILD set and another for computing an ILD set of minimum cardinality, both with time complexity O(n 2 ).