Extremal graphs for threshold metric dimension
T. Datema (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J. Komjáthy – Mentor (TU Delft - Applied Probability)
A. Bishnoi – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
More Info
expand_more
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.
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.