The Identifying Code problem on P₄-tidy graphs

2013/12/14 by Graciela Nasini, Nasini, Graciela, Pablo Torres +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1312.4059

This paper has been withdrawn by the authors due to academic reasons

arxiv created 2014/12/09 · arxiv updated 2014/12/10

Abstract

In this paper we first analyze the behaviour of the identifying code number under union and join operations in graphs. This study forced us to analyze three new parameters related to identifying codes, dominating sets and total dominating sets of the complementary graph. We obtain closed formulas for these parameters on spider and quasi-spider graphs. These results easily derive in a linear dynamic programming-based algorithm for the Identifying Code problem for P₄-tidy graphs.

Related

• On lower bounds for cardinalities of several separating-dominating codes in graphs
• Identifying codes and locating-dominating sets on paths and cycles
• On minimum identifying codes in some Cartesian product graphs
• On open-separating dominating codes in graphs
• Progress on Self Identifying Codes