A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On {l}-Metric Dimensions in Graphs
Tekijät: Hakanen A, Laihonen T
Kustantaja: IOS PRESS
Julkaisuvuosi: 2018
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: FUNDAMENTA INFORMATICAE
Lehden akronyymi: FUND INFORM
Vuosikerta: 162
Numero: 2-3
Aloitussivu: 143
Lopetussivu: 160
Sivujen määrä: 18
ISSN: 0169-2968
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-2018-1718
Tiivistelmä
A subset S of vertices is a resolving set in a graph if every vertex has a unique array of distances to the vertices of S. Consequently, we can locate any vertex of the graph with the aid of the distance arrays. The problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we consider sets S which can locate several, say up to l, vertices in a graph. These sets are called {l}-resolving sets and the smallest cardinality of such a set is the {l}-metric dimension of the graph. In this paper, we will give the {l}-metric dimensions for trees and king grids. We will show that there are certain vertices that necessarily belong to an {l}-resolving set. Moreover, we will classify all graphs whose {l}-metric dimension equals l.
A subset S of vertices is a resolving set in a graph if every vertex has a unique array of distances to the vertices of S. Consequently, we can locate any vertex of the graph with the aid of the distance arrays. The problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we consider sets S which can locate several, say up to l, vertices in a graph. These sets are called {l}-resolving sets and the smallest cardinality of such a set is the {l}-metric dimension of the graph. In this paper, we will give the {l}-metric dimensions for trees and king grids. We will show that there are certain vertices that necessarily belong to an {l}-resolving set. Moreover, we will classify all graphs whose {l}-metric dimension equals l.
Turun yliopiston Tutkimustietojärjestelmän portaali