Independent locating-dominating sets in P4-sparse graphs
Dayllon Vinícius Xavier Lemos, Márcia Rodrigues Cappelle, Erika M. M. Coelho, Les R. Foulds, Humberto José Longo · 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. NG(u)∩S ≠ NG(v)∩S, ∀ u, v ∈ V (G)\S, u≠ v. We study ILD sets in P4-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(n2).