Truncated metric dimension of graphs : master's thesis

Mrhar, Nik (author), Bujtás, Csilla (mentor)

The $k$-truncated metric dimension is a variant of the metric dimension in which distances greater than $k$ are treated as equal. In this thesis, we study the $k$-truncated metric dimension of several graph classes. We determine its exact value for tadpole graphs, subdivided stars, and multi-tailed tadpole graphs whose pendant paths have order at least $k+1$ after applying the reduction. We also consider generalised tadpole graphs, in which pendant paths satisfying the same condition may be attached to arbitrary vertices of a cycle. For this class, we develop a greedy algorithm for constructing a $k$-truncated resolving set. We prove the correctness of the algorithm, show that it runs in polynomial time for fixed $k$, and establish an approximation ratio of $4/3$.

• Language: English
• Keywords: k-truncated metric dimension, resolving set, tadpole graph, subdivided star, multi-tailed tadpole graph, generalised tadpole graph, approximation algorithm
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2026
• PID: 20.500.12556/RUL-188447
• UDC: 519.17
• COBISS.SI-ID: 291804675
• Publication date in RUL: 23.09.2026

Secondary language

• Language: Slovenian
• Title: Prirezana metrična dimenzija grafov

Abstract

$k$-Prirezana metrična dimenzija je različica metrične dimenzije, pri kateri se vse razdalje, večje od $k$, obravnavajo kot enake. V magistrskem delu preučujemo $k$-prirezano metrično dimenzijo več razredov grafov. Določimo njeno natančno vrednost za cikle s pripetimi potmi in subdividirane zvezde ter za cikle z več pripetimi potmi, pri katerih imajo vse pripete poti po uporabi redukcije red vsaj $k+1$. Obravnavamo tudi posplošene cikle s pripetimi potmi, pri katerih pripete poti zadostujejo enakim pogojem in so lahko pripete na poljubna vozlišča cikla. Za ta razred razvijemo algoritem za konstrukcijo $k$-prirezane razločevalne množice. Dokažemo pravilnost algoritma, pokažemo, da za fiksen $k$ deluje v polinomskem času, ter določimo njegovo aproksimacijsko razmerje $4/3$.

• Keywords: k-prirezana metrična dimenzija, razločevalna množica, cikel s pripeto potjo, subdividirana zvezda, cikel z več pripetimi potmi, posplošeni cikel s pripetimi potmi, aproksimacijski algoritem