Truncated metric dimension of graphs : master's thesis

Mrhar, Nik (avtor), 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$.

• Jezik: Angleški jezik
• Ključne besede: k-truncated metric dimension, resolving set, tadpole graph, subdivided star, multi-tailed tadpole graph, generalised tadpole graph, approximation algorithm
• Vrsta gradiva: Magistrsko delo/naloga
• Tipologija: 2.09 - Magistrsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2026
• PID: 20.500.12556/RUL-188447
• UDK: 519.17
• COBISS.SI-ID: 291804675
• Datum objave v RUL: 23.09.2026

Sekundarni jezik

• Jezik: Slovenski jezik
• Naslov: Prirezana metrična dimenzija grafov

Izvleček

$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$.

• Ključne besede: 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