Search

Several different types of identification problems have been already 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 of the graph, often referred to as a \emph{code}. To study such problems under a unifying point of view, reformulations of the already studied problems in terms of covering problems in suitably constructed hypergraphs have been provided. Analyzing these hypergraph representations, we introduce a new separation property, called \emph{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 \emph{full-separating-dominating codes} (or \emph{FD-codes} for short) and \emph{full-separating-total-dominating codes} (or \emph{FTD-codes} for short), respectively. We address the conditions for the existence of FD- and FTD-codes, bounds for their size and their relation to codes of the other types. We 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-complete to decide if they are equal for a given graph in general. We find the exact values of minimum cardinalities of the FD- and FTD-codes on some familiar graph classes like paths, cycles, half-graphs and spiders. This helps us compare the two codes with other codes on these graph families thereby exhibiting extremal cases for several lower bounds.

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$ such that the neighbourhoods of all vertices of $G$ have distinct intersections with $C$. Such a dominating and separating set $C$ is often referred to as a \emph{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 \emph{open-separating dominating code}, or \emph{OSD-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 OSD-codes. Due to the emergence of a close and yet difficult to establish relation of the OSD-codes with another well-studied code in the literature called open locating dominating codes, or OLD-codes for short, we compare the two on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OSD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OSD-codes, again in relation to OLD-codes of some graph families already studied in this context.

We consider the following variants of the classical minimum dominating set problem in graphs: locating-dominating set, locating total-dominating set and open locating-dominating set. All these problems are known to be hard for general graphs. A typical line of attack, therefore, is to either determine the minimum cardinalities of such sets in general or to establish bounds on these minimum cardinalities in special graph classes. In this paper, we study the minimum cardinalities of these variants of the dominating set under a graph operation defined by Mycielski in~\cite{Mycielski1955} and is called the Mycielski construction. We provide some general lower and upper bounds on the minimum sizes of the studied sets under the Mycielski construction. We apply the Mycielski construction to stars, paths and cycles in particular, and provide lower and upper bounds on the minimum cardinalities of such sets in these graph classes. Our results either improve or attain the general known upper bounds.

We study upper bounds on the size of optimum locating-total dominating sets in graphs. A set $S$ of vertices of a graph $G$ is a locating-total dominating set if every vertex of $G$ has a neighbor in $S$, and if any two vertices outside $S$ have distinct neighborhoods within $S$. The smallest size of such a set is denoted by $\gamma^L_t(G)$. It has been conjectured that $\gamma^L_t(G)\leq\frac{2n}{3}$ holds for every twin-free graph $G$ of order $n$ without isolated vertices. We prove that the conjecture holds for cobipartite graphs, split graphs, block graphs, subcubic graphs and outerplanar graphs.