dc.contributor.advisor |
Fricke, G.H. (Prof.)
|
en |
dc.contributor.advisor |
Frick, M. (Prof.)
|
en |
dc.contributor.author |
Skaggs, Robert Duane
|
en |
dc.date.accessioned |
2009-08-25T11:01:38Z |
|
dc.date.available |
2009-08-25T11:01:38Z |
|
dc.date.issued |
2009-08-25T11:01:38Z |
|
dc.date.submitted |
2007-02-28 |
en |
dc.identifier.citation |
Skaggs, Robert Duane (2009) Identifying vertices in graphs and digraphs, University of South Africa, Pretoria, <http://hdl.handle.net/10500/2226> |
en |
dc.identifier.uri |
http://hdl.handle.net/10500/2226 |
|
dc.description.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. |
en |
dc.format.extent |
1 online resource (v, 80 leaves) |
|
dc.language.iso |
en |
en |
dc.subject |
Oriented graph |
en |
dc.subject |
Nordhaus-Gaddum results |
en |
dc.subject |
Graph complement |
en |
dc.subject |
Criticality |
en |
dc.subject |
Identifying code |
en |
dc.subject |
Domination |
en |
dc.subject |
Graph theory |
en |
dc.subject.ddc |
511.5 |
|
dc.subject.lcsh |
Graph theory |
|
dc.subject.lcsh |
Graphic methods |
|
dc.subject.lcsh |
Directed graphs |
|
dc.title |
Identifying vertices in graphs and digraphs |
en |
dc.type |
Thesis |
en |
dc.contributor.email |
djagegjj@unisa.ac.za |
en |
dc.description.department |
Mathematical Sciences |
en |
dc.description.degree |
PhD (Mathematics) |
en |