Distance measures, independence number and chromatic number
| dc.contributor.author | Moholane, Letlhogonolo | |
| dc.contributor.co-supervisor | Jonck, Betsie | |
| dc.contributor.supervisor | Mukwembi, Simon | |
| dc.date.accessioned | 2024-10-20T19:32:52Z | |
| dc.date.available | 2024-10-20T19:32:52Z | |
| dc.date.issued | 2023-03 | |
| dc.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. | |
| dc.description.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. | |
| dc.description.sponsorship | National Research Foundation (NRF-CPRR). | |
| dc.description.submitter | MM2024 | |
| dc.faculty | Faculty of Science | |
| dc.identifier | 0000-0002-4446-3387 | |
| dc.identifier.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 | |
| dc.identifier.uri | https://hdl.handle.net/10539/41756 | |
| dc.language.iso | en | |
| dc.publisher | University of the Witwatersrand, Johannesburg | |
| dc.rights | ©2023 University of the Witwatersrand, Johannesburg. All rights reserved. The copyright in this work vests in the University of the Witwatersrand, Johannesburg. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of University of the Witwatersrand, Johannesburg. | |
| dc.rights.holder | University of the Witwatersrand, Johannesburg | |
| dc.school | School of Mathematics | |
| dc.subject | Average distance | |
| dc.subject | Average eccentricity | |
| dc.subject | Order | |
| dc.subject | Independence number | |
| dc.subject | Chromatic number | |
| dc.subject | UCTD | |
| dc.subject.other | SDG-9: Industry, innovation and infrastructure | |
| dc.title | Distance measures, independence number and chromatic number | |
| dc.type | Dissertation |