Extremal graphs for threshold metric dimension

Bachelor thesis (2022)

Authors

T. Datema Electrical Engineering, Mathematics and Computer Science

Contributors

J. Komjáthy Applied Probability - EEMCS (mentor)
A. Bishnoi Discrete Mathematics and Optimization - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Tobias Datema
More Info
expand_more

Published Date

14-07-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.

Files

Report_tdatema.pdf
(.pdf | 1.25 Mb)