Some links between identifying codes and separating, dominating and total dominating sets in graphs

GRACIELA NASINI; PABLO TORRES

Electronic Notes in Discrete Mathematics

Elsevier

Año: 2015 p. 181 - 186

1571-0653

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 $P_4$-tidy graphs.