|
Abstract:
|
The closed neighbourhood of a vertex in a graph is the vertex together with
the set of adjacent vertices. A di®erentiating-dominating set, or identifying
code, is a collection of vertices whose intersection with the closed neighbour-
hoods of each vertex is distinct and nonempty. A di®erentiating-dominating
set in a graph serves to uniquely identify all the vertices in the graph.
Chapter 1 begins with the necessary de¯nitions and background results
and provides motivation for the following chapters. Chapter 1 includes a
summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de-
¯nes co-distinguishable graphs and determines bounds on the number of
edges in graphs which are distinguishable and co-distinguishable while Chap-
ter 3 describes the maximum number of vertices needed in order to identify
vertices in a graph, and includes some Nordhaus-Gaddum type results for
the sum and product of the di®erentiating-domination number of a graph
and its complement.
Chapter 4 explores criticality, in which any minor modi¯cation in the
edge or vertex set of a graph causes the di®erentiating-domination number
to change. Chapter 5 extends the identi¯cation parameters to allow for
orientations of the graphs in question and considers the question of when
adding orientation helps reduce the value of the identi¯cation parameter. We
conclude with a survey of complexity results in Chapter 6 and a collection
of interesting new research directions in Chapter 7. |
