Distances in and between graphs.

UKZN ResearchSpace

Show simple item record

dc.contributor.advisor Swart, Henda C.
dc.creator Bean, Timothy Jackson.
dc.date.accessioned 2012-07-23T13:24:46Z
dc.date.available 2012-07-23T13:24:46Z
dc.date.created 1991
dc.date.issued 1991
dc.identifier.uri http://hdl.handle.net/10413/6065
dc.description Thesis (M.Sc.)-University of Natal, 1991. en
dc.description.abstract Aspects of the fundamental concept of distance are investigated in this dissertation. Two major topics are discussed; the first considers metrics which give a measure of the extent to which two given graphs are removed from being isomorphic, while the second deals with Steiner distance in graphs which is a generalization of the standard definition of distance in graphs. Chapter 1 is an introduction to the chapters that follow. In Chapter 2, the edge slide and edge rotation distance metrics are defined. The edge slide distance gives a measure of distance between connected graphs of the same order and size, while the edge rotation distance gives a measure of distance between graphs of the same order and size. The edge slide and edge rotation distance graphs for a set S of graphs are defined and investigated. Chapter 3 deals with metrics which yield distances between graphs or certain classes of graphs which utilise the concept of greatest common subgraphs. Then follows a discussion on the effects of certain graph operations on some of the metrics discussed in Chapters 2 and 3. This chapter also considers bounds and relations between the metrics defined in Chapters 2 and 3 as well as a partial ordering of these metrics. Chapter 4 deals with Steiner distance in a graph. The Steiner distance in trees is studied separately from the Steiner distance in graphs in general. The concepts of eccentricity, radius, diameter, centre and periphery are generalised under Steiner distance. This final chapter closes with an algorithm which solves the Steiner problem and a Heuristic which approximates the solution to the Steiner problem. en
dc.language.iso en_ZA en
dc.subject Graph Theory. en
dc.subject Theses--Mathematics. en
dc.title Distances in and between graphs. en
dc.type Thesis en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UKZN ResearchSpace

Advanced Search


My Account