Extremal graphs for threshold metric dimension

Extremal graphs for threshold metric dimension

Datema, Tobias (TU Delft Electrical Engineering, Mathematics and Computer Science)

Komjáthy, J. (mentor)
Bishnoi, A. (graduation committee)

Delft University of Technology

Applied Mathematics

AM3000

2022-07-14

In this thesis, we consider the threshold metric dimension problem of graphs, related to and motivated by source detection.
We construct a graph G = (V,E) for a given set of sensors of size m: {s1, s2, ..., sm} and a range k > 0. We want that each node v ∈ V has a unique combination of distances (dk (s1, v),dk (s2, v), ...,dk (sm, v)), where dk is the distance function in a graph limited by the range k (the distance is denoted as being ∞ if the distance is larger than k). Our aim in this thesis is to construct such a graph that is extremal in size, that is: the vertex set V is as large as possible. We shall give such constructions with proof for optimality up to k = 3 and general m
and a different construction with incomplete proof for optimality for general k and m. For any construction we will prove that each vertex is uniquely identified.
Furthermore, we will compare our results to another paper with a similar conclusion about the extremal size of graphs with metric dimension m and a given diameter D.

graph theory
metric dimension
threshold metric dimension
extremal
threshold

http://resolver.tudelft.nl/uuid:49f39b66-1c8a-4699-845d-cfe9f4138a41

Student theses

bachelor thesis

© 2022 Tobias Datema