2024/02/05 by Dipayan Chakraborty, Chakraborty, Dipayan, Annegret K. Wagler +1
Computer Science · #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2402.03015
openalex publication_date 2024/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is to choose a suitable dominating set C of a graph G which is also separating in the sense that the neighbourhoods of any two distinct vertices of G have distinct intersections with C. Such a dominating and separating set C of a graph is often referred to as a code in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called open-separating dominating code, or OD-code for short, is a dominating set and uses open neighbourhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OD-codes. Due to the emergence of a close and yet difficult to establish relation of the OD-code with another well-studied code in the literature called open (neighborhood)-locating dominating code (referred to as the open-separating total-dominating code and abbreviated as OTD-code in this paper), we compare the two codes on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OD-codes, again in relation to OTD-codes of some graph families already studied in this context.