Institutional Repository

# Identifying vertices in graphs and digraphs

 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, 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 en 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. 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
﻿