Wyniki wyszukiwania - BazTech

1

All metric bases and fault-tolerant metric dimension for square of grid

Saha Laxman, Basak Mithun, Tiwary Kalishankar

Opuscula Mathematica

|

2022

|

Vol. 42, no. 1

93--111

EN

For a simple connected graph G = (V,E) and an ordered subset W = {w1, w2, . . . , wk} of V , the code of a vertex v ∈ V , denoted by code(v), with respect to W is a k-tuple (d(v, w1), . . . , d(v, wk)), where d(v, wt) represents the distance between v and wt. The set W is called a resolving set of G if code(u) ≠ code(v) for every pair of distinct vertices u and v. A metric basis of G is a resolving set with the minimum cardinality. The metric dimension of G is the cardinality of a metric basis and is denoted by β(G). A set F ⊂ V is called fault-tolerant resolving set of G if F \ {v} is a resolving set of G for every v ∈ F. The fault-tolerant metric dimension of G is the cardinality of a minimal fault-tolerant resolving set. In this article, a complete characterization of metric bases for G2 mn has been given. In addition, we prove that the fault-tolerant metric dimension of G2 mn is 4 if m + n is even. We also show that the fault-tolerant metric dimension of G2 mn is at least 5 and at most 6 when m + n is odd.

2

Metric dimension of Andrasfai graphs

Pejman S. Batool, Payrovi Shiroyeh, Behtoei Ali

Opuscula Mathematica

|

2019

|

Vol. 39, no. 3

415--423

EN

A set W ⊆ V(G) is called a resolving set, if for each pair of distinct vertices u,v ∈ V(G) there exists t ∈ W such that d(u,t) ≠ d(v,t), where d(x,y) is the distance between vertices x and y. The cardinality of a minimum resolving set for G is called the metric dimension of G and is denoted by dimM(G). This parameter has many applications in different areas. The problem of finding metric dimension is NP-complete for general graphs but it is determined for trees and some other important families of graphs. In this paper, we determine the exact value of the metric dimension of Andrasfai graphs, their complements and [formula]. Also, we provide upper and lower bounds for [formula].

3

On {l}-Metric Dimensions in Graphs

Hakanen A., Laihonen T.

Fundamenta Informaticae

|

2018

|

Vol. 162, nr 2/3

143--160

EN

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.