Institutional Repository

Identifying vertices in graphs and digraphs

Show simple item record

dc.contributor.advisor Fricke, G.H. (Prof.) en
dc.contributor.advisor Frick, M. (Prof.) en Skaggs, Robert Duane en 2009-08-25T11:01:38Z 2009-08-25T11:01:38Z 2009-08-25T11:01:38Z 2007-02-28 en
dc.identifier.citation Skaggs, Robert Duane (2009) Identifying vertices in graphs and digraphs, University of South Africa, Pretoria, <> en
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 en
dc.description.department Mathematical Sciences en PhD (Mathematics) en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account