Domination and distance measures in graphs

Loading...
Thumbnail Image

Date

Journal Title

Journal ISSN

Volume Title

Publisher

University of the Witwatersrand, Johannesburg

Abstract

Let G be a graph. A dominating set of G is a set of vertices such that every vertex in G is either in the set or adjacent to a vertex in the set. The domination number is the size of a smallest dominating set. The minimum degree of graph G is the smallest number of edges incident to any single vertex in the graph. In graph G, the distance between two vertices is the length of a shortest path between them. The eccentricity of a vertex in G is the greatest distance from that vertex to any other vertex in the graph. The radius of G is the smallest eccentricity among all eccentricities of ver- tices of the graph. The diameter of G is the largest eccentricity amongst all eccentricities of vertices in the graph. The boundary of G consists of all vertices with the highest eccentricity. The average distance of G is mean of all distances between vertex pairs. This dissertation explores the in- tricate relationships between domination, distance-based parameters, and minimum degree in graphs. The first part of the dissertation provides bounds on the domination num- ber in terms of radius, order, and minimum degree of the graph. The second part focuses on bounds on domination number involving distances between vertices and the eccentricity of the boundary of the graph. Finally, the third part discusses upper bounds on average distance in terms of the domination number of the graph.

Description

A research report submitted in fulfillment of the requirements for the Master of Science in Mathematics, in the Faculty of Science, School of Mathematics, University of the Witwatersrand, Johannesburg, 2025

Citation

Matshisevhe, Tshepo. (2025). Domination and distance measures in graphs [Master’s dissertation, University of the Witwatersrand, Johannesburg]. WIReDSpace. https://hdl.handle.net/10539/50265

Endorsement

Review

Supplemented By

Referenced By