The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations

G Argiroffo , S. Bianchi (1) , Y Lucarini , Annegret K. Wagler (2)

1 OAA - INAF - Osservatorio Astrofisico di Arcetri
2 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes

The problems of determining minimum identifying, locating-dominating, open locating-dominating or locating total-dominating codes in a graph G are variations of the classical minimum dominating set problem in G and are all known to be hard for general graphs. A typical line of attack is therefore to determine the cardinality of minimum such codes in special graphs. In this work we study the change of minimum such codes under three operations in graphs: adding a universal vertex, taking the generalized corona of a graph, and taking the square of a graph. We apply these operations to paths and cycles which allows us to provide minimum codes in most of the resulting graph classes.

Domaines: Mathématique discrète [cs.DM]; Recherche opérationnelle [math.OC]; Combinatoire [math.CO]

G Argiroffo, S. Bianchi, Y Lucarini, Annegret K. Wagler. The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations. LAGOS 2019, Jun 2019, Belo Horizonte, Brazil. pp.135-145, ⟨10.1016/j.entcs.2019.08.013⟩. ⟨hal-02017469⟩