The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations
| Autor: | Gabriela R. Argiroffo, Annegret Wagler, Yanina Lucarini, Silvia M. Bianchi |
|---|---|
| Přispěvatelé: | INAF - Osservatorio Astrofisico di Arcetri (OAA), Istituto Nazionale di Astrofisica (INAF), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Vertex (graph theory)
Discrete mathematics General Computer Science Computer science 020207 software engineering 0102 computer and information sciences 02 engineering and technology [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 16. Peace & justice 01 natural sciences Graph Theoretical Computer Science Vertex (geometry) Minimum dominating set Cardinality 010201 computation theory & mathematics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 0202 electrical engineering electronic engineering information engineering Graph operations MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | LAGOS Electronic Notes in Theoretical Computer Science LAGOS 2019 LAGOS 2019, Jun 2019, Belo Horizonte, Brazil. pp.135-145, ⟨10.1016/j.entcs.2019.08.013⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|