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

Abstract : 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.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.uca.fr/hal-02017469
Contributor : Annegret Wagler <>
Submitted on : Wednesday, February 13, 2019 - 11:02:03 AM
Last modification on : Monday, January 20, 2020 - 12:14:06 PM
Long-term archiving on: Tuesday, May 14, 2019 - 1:53:58 PM

File

ABLW_Lagos19_HAL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02017469, version 1

Collections

Citation

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. 2019. ⟨hal-02017469⟩

Share

Metrics

Record views

36

Files downloads

59