Distance measures, independence number and chromatic number
Date
2023-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of the Witwatersrand, Johannesburg
Abstract
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.
Description
A dissertation submitted in fulfilment of the requirements for the degree of Master of Science, to the Faculty of Science, School of Mathematics, University of the Witwatersrand, Johannesburg, 2023.
Keywords
Average distance, Average eccentricity, Order, Independence number, Chromatic number, UCTD
Citation
Moholane, Letlhogonolo. (2023). Distance measures, independence number and chromatic number. [Master's dissertation, University of the Witwatersrand, Johannesburg]. https://hdl.handle.net/10539/41756