Repository logo
 

Aspects of graph vulnerability.

dc.contributor.advisorSwart, Hendrika Cornelia Scott.
dc.contributor.advisorOellermann, Ortrud Ruth.
dc.contributor.authorDay, David Peter.
dc.date.accessioned2012-01-20T09:53:35Z
dc.date.available2012-01-20T09:53:35Z
dc.date.created1994
dc.date.issued1994
dc.descriptionThesis (Ph.D.)-University of Natal, 1994.en
dc.description.abstractThis dissertation details the results of an investigation into, primarily, three aspects of graph vulnerability namely, l-connectivity, Steiner Distance hereditatiness and functional isolation. Following the introduction in Chapter one, Chapter two focusses on the l-connectivity of graphs and introduces the concept of the strong l-connectivity of digraphs. Bounds on this latter parameter are investigated and then the l-connectivity function of particular types of graphs, namely caterpillars and complete multipartite graphs as well as the strong l-connectivity function of digraphs, is explored. The chapter concludes with an examination of extremal graphs with a given l-connectivity. Chapter three investigates Steiner distance hereditary graphs. It is shown that if G is 2-Steiner distance hereditary, then G is k-Steiner distance hereditary for all k≥2. Further, it is shown that if G is k-Steiner distance hereditary (k≥ 3), then G need not be (k - l)-Steiner distance hereditary. An efficient algorithm for determining the Steiner distance of a set of k vertices in a k-Steiner distance hereditary graph is discussed and a characterization of 2-Steiner distance hereditary graphs is given which leads to an efficient algorithm for testing whether a graph is 2-Steiner distance hereditary. Some general properties about the cycle structure of k-Steiner distance hereditary graphs are established and are then used to characterize 3-Steiner distance hereditary graphs. Chapter four contains an investigation of functional isolation sequences of supply graphs. The concept of the Ranked supply graph is introduced and both necessary and sufficient conditions for a sequence of positive nondecreasing integers to be a functional isolation sequence of a ranked supply graph are determined.en
dc.identifier.urihttp://hdl.handle.net/10413/4864
dc.language.isoenen
dc.subjectGraph theory.en
dc.subjectTheses--Mathematics.en
dc.titleAspects of graph vulnerability.en
dc.typeThesisen

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Day_Peter_David_1994.pdf
Size:
4.55 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.64 KB
Format:
Item-specific license agreed upon to submission
Description: