Eccentricity-based fault tolerance in graphs

Wade, Michael

Eccentricity-based fault tolerance in graphs

Thesis / Dissertation

2026

Publisher

University of Cape Town

Department

Department of Mathematics and Applied Mathematics

Faculty

Faculty of Science

Abstract

The eccentricity of a vertex in a graph is the maximum length of a shortest path from that vertex to any other vertex in the graph. The eccentricity index of a graph is the sum of the eccentricities of the vertices in the graph. A fault in a graph is a vertex or edge deletion. In this thesis, we study eccentricity-based measures and properties of fault tolerance in graphs. Specifically, we study the change in the eccentricity of a vertex and the eccentricity index of a graph after edge or vertex deletions. We begin by discussing literature on edge-deleted eccentricity and edge-deleted eccentricity stable graphs. We then introduce vertex-deleted eccentricity and the average vertex-deleted eccentricity index of a graph and prove novel results regarding these concepts. Finally, we conclude by assessing the fault tolerance of common graphs in computer network design based on the measures discussed previously

Keywords

eccentricity

graph, vertex

Reference:

Collections

Masters

Full item page