Electronic Theses and Dissertations (Masters)

Permanent URI for this collection

Now showing 1 - 1 of 1

Distance measures, independence number and chromatic number
(University of the Witwatersrand, Johannesburg, 2023-03) Moholane, Letlhogonolo; Jonck, Betsie; Mukwembi, Simon
There are numerous parameters in graph theory. In this dissertation, we pay a special attention to average distance, independence number, average eccentricity, order and the chromatic number of a graph. In 1975, Doyle and Graver proved an upper bound on the average distance with respect to the order of the graph. This gave rise to studies that focus on upper and lower bounds on average distance in terms of other graph parameters. Approximately, three decades after Doyle and Graver proved their result, Dankelmann, Goddard, and Swart in 2004 produced a study that gave an upper bound on average eccentricity in terms of minimum degree and order of the graph, initiating studies that focus on giving bounds on average eccentricity with respect to other known graph parameters. In this dissertation, we investigate bounds on average eccentricity and on average distance. We give upper bounds on average eccentricity in terms of independence number of the graph and order of the graph. Then, we present bounds on average eccentricity when order and chromatic number of the graph are prescribed. The second part of the dissertation is dedicated to presenting upper bounds on average distance with respect to independence number and order of the graph, and again, in terms of chromatic number and order of the graph.