Independent locating-dominating sets in P4-sparse graphs
Resumo
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).
Referências
Bravo, R. S., Klein, S., Nogueira, L. T., and Protti, F. (2011). Characterization and recognition of P4-sparse graphs partitionable into k independent sets and ℓ cliques. Discrete Applied Mathematics, 159(4):165–173.
Foucaud, F., Mertzios, G. B., Naserasr, R., Parreau, A., and Valicov, P. (2017). Identification, location–domination and metric dimension on interval and permutation graphs. i. bounds. Theoretical Computer Science, 668:43–58.
Jamison, B. and Olariu, S. (1992a). Recognizing P4-sparse graphs in linear time. SIAM Journal on Computing, 21(2):381–406.
Jamison, B. and Olariu, S. (1992b). A tree representation for P4-sparse graphs. Discrete Applied Mathematics, 35(2):115–129.
Jamison, B. and Olariu, S. (1995). Linear time optimization algorithms for P4-sparse graphs. Discrete Applied Mathematics, 61(2):155–175.
Jean, D. (2023). Watching systems, identifying, locating-dominating and discriminating codes in graphs. [link]. Last accessed on: February 05, 2025.
Ray, S., Starobinski, D., Trachtenberg, A., and Ungrangsi, R. (2004). Robust location detection with sensor networks. IEEE Journal on Selected Areas in Communications, 22(6):1016–1025.
Slater, P. J. (1987). Domination and location in acyclic graphs. Networks, 17(1):55–64.
Slater, P. J. and Sewell, J. L. (2018). Independent locating-dominating sets and independent identifying codes in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 104:261–272.
Foucaud, F., Mertzios, G. B., Naserasr, R., Parreau, A., and Valicov, P. (2017). Identification, location–domination and metric dimension on interval and permutation graphs. i. bounds. Theoretical Computer Science, 668:43–58.
Jamison, B. and Olariu, S. (1992a). Recognizing P4-sparse graphs in linear time. SIAM Journal on Computing, 21(2):381–406.
Jamison, B. and Olariu, S. (1992b). A tree representation for P4-sparse graphs. Discrete Applied Mathematics, 35(2):115–129.
Jamison, B. and Olariu, S. (1995). Linear time optimization algorithms for P4-sparse graphs. Discrete Applied Mathematics, 61(2):155–175.
Jean, D. (2023). Watching systems, identifying, locating-dominating and discriminating codes in graphs. [link]. Last accessed on: February 05, 2025.
Ray, S., Starobinski, D., Trachtenberg, A., and Ungrangsi, R. (2004). Robust location detection with sensor networks. IEEE Journal on Selected Areas in Communications, 22(6):1016–1025.
Slater, P. J. (1987). Domination and location in acyclic graphs. Networks, 17(1):55–64.
Slater, P. J. and Sewell, J. L. (2018). Independent locating-dominating sets and independent identifying codes in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 104:261–272.
Publicado
20/07/2025
Como Citar
LEMOS, Dayllon Vinícius Xavier; CAPPELLE, Márcia Rodrigues; COELHO, Erika Morais Martins; FOULDS, Leslie Richard; LONGO, Humberto José.
Independent locating-dominating sets in P4-sparse graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 41-45.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.8228.
