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. / Mathematical Sciences / PhD (Mathematics)
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:unisa/oai:umkn-dsp01.int.unisa.ac.za:10500/2226 |
| Date | 28 February 2007 |
| Creators | Skaggs, Robert Duane |
| Contributors | Fricke, G.H. (Prof.), Frick, M. (Prof.), djagegjj@unisa.ac.za |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 1 online resource (v, 80 leaves) |
Page generated in 0.0023 seconds