Chapter I begins with a brief history of the topic of greatest common subgraphs.
Then we provide a summaiy of the work done on some variations of greatest common
subgraphs. Finally, in this chapter we present results previously obtained on greatest
common divisors and least common multiples of graphs.
In Chapter II the concepts of prime graphs, prime divisors of graphs, and primeconnected
graphs are presented. We show the existence of prime trees of any odd size
and the existence of prime-connected trees that are not prime having any odd composite
size. Then the number of prime divisors in a graph is studied. Finally, we present
several results involving the existence of graphs whose size satisfies some prescribed
condition and which contains a specified number of prime divisors.
Chapter III presents properties of greatest common divisors and least common
multiples of graphs. Then graphs with a prescribed number of greatest common
divisors or least common multiples are studied.
In Chapter IV we study the sizes of greatest common divisors and least common
multiples of specified graphs. We find the sizes of greatest common divisors and least
common multiples of stars and that of stripes. Then the size of greatest common
divisors and least common multiples of paths and complete graphs are investigated. In
particular, the size of least common multiples of paths versus K3 or K4 are
determined. Then we present the greatest common divisor index of a graph and we
determine this parameter for several classes of graphs.
iii
In Chapter V greatest common divisors and least common multiples of digraphs
are introduced. The existence of least common mutliples of two stars is established,
and the size of a least common multiple is found for several pairs of stars. Finally, we
present the concept of greatest common divisor index of a digraph and determine it for
several classes of digraphs.
iv / Mathematical Sciences / Ph. D. (Mathematical sciences)
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:unisa/oai:uir.unisa.ac.za:10500/9306 |
| Date | 11 1900 |
| Creators | Saba, Farrokh |
| Contributors | Mynhardt, C. M. |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 1 online resource (iv, 132 leaves) |
| Rights | University of South Africa |
Page generated in 0.0014 seconds