On Full-Separating Sets in Graphs
摘要
Several different types of identification problems have been studied in the literature, where the objective is to distinguish any two vertices of a graph by their unique neighborhoods in a suitably chosen dominating or total-dominating set, often referred to as a code. To study such problems under a unifying point of view, reformulations in terms of covering problems in suitably constructed hypergraphs have been provided. Analyzing these hypergraph representations, we introduce a new separation property, called full-separation, which has not yet been considered in the literature so far. We study it in combination with both domination and total-domination, and call the resulting codes full-separating dominating codes (or FD-codes for short) and full-separating total-dominating codes (or FTD-codes for short), respectively. We address the conditions for the existence of FD- and FTD-codes, bounds for their size, their relation to codes of the other types and present some extremal cases for these bounds and relations. We further show that the problems of determining an FD- or an FTD-code of minimum cardinality in a graph is NP-hard. We also show that the cardinalities of minimum FD- and FTD-codes differ by at most one, but that it is NP-hard to decide if they are equal for a given graph in general.