info:eu-repo/semantics/article
Some links between identifying codes and separating, dominating and total dominating sets in graphs
Fecha
2015-12Registro en:
Nasini, Graciela Leonor; Torres, Pablo Daniel; Some links between identifying codes and separating, dominating and total dominating sets in graphs; Elsevier; Electronic Notes in Discrete Mathematics; 50; 12-2015; 181-186
1571-0653
CONICET Digital
CONICET
Autor
Nasini, Graciela Leonor
Torres, Pablo Daniel
Resumen
In the search for a dynamic programming-based algorithm derived from the modular decomposition of graphs, we analyze the behavior of the identifying code number under disjoint union and join operations. This study lead us to investigate the behavior of new parameters related to separating, dominating and total dominating sets under the same operations. The obtained results and the modular decomposition of graphs easily result in a dynamic programming-based algorithm to calculate the identifying code number (and the related parameters) of a graph from the parameter values of its modular subgraphs. In particular, we obtain closed formulas for the parameters on spider and quasi-spider graphs which allow us to derive a simple and easy-to-implement linear time algorithm to obtain the identifying code number (and the related parameters) of P4-tidy graphs.