Identification problems in graphs are those which deal with separating one vertex of the graph from another. One of the most well studied formulations of such problems is by using dominating sets. A dominating set is a vertex subset S of a graph G such that any vertex not is S must have a neighbor in S. Using such sets as a combinatorial tool, pairs of vertices can be separated by finding a dominating set such that any two distinct vertices have distinct sets of neighbors in the set. In this thesis, we study such identification problems in graphs based on dominating and total-dominating sets (a stronger variant of dominating sets). Also varying the types of (distinct) neighborhoods by which the vertices are separated, we look at four separating properties, one of which is newly introduced as part of this PhD. Thus, in combination with the two dominating properties, we study at eight separating-dominating sets (often called codes) in graphs. The objective of such studies is to minimize the cardinalities of the codes and we call such a minimum cardinality to be a code number. The thesis has both structural and algorithmic results. In the structural part, we study general bounds on all the eight codes and pairwise compare their code numbers to provide a complete scheme of their relations. We also study several conjectures from the literature on bounds for these code numbers and prove them on many well-known graph classes. In the algorithmic part of the thesis, we prove that for the codes newly introduced as part of this thesis, finding a minimum code and also establishing some interesting pairwise relations is NP-complete. Moreover, for a well-known code called the locating dominating code (or LD-code), we look at the problem parameterized by some natural and structural parameters, in terms of which, we devise several FPT algorithms and also provide tight lower bounds on the algorithmic running time of the problem under some well-accepted computational hardness hypotheses.

Le jury est composé de :