wang, juan miao, lianying liu, yunlong

Let G = ( V ( G ) , E ( G ) ) be a connected graph. An ordered set W &sub / V ( G ) is a resolving set for G if every vertex of G is uniquely determined by its vector of distances to the vertices in W. The metric dimension of G is the minimum cardinality of a resolving set. In this paper, we characterize the graphs of metric dimension n &minus / 3 ...

Shao, Zehui Wu, Pu Zhu, Enqiang Chen, Lanxiang
Published in
Sensors (Basel, Switzerland)

The concept of a metric dimension was proposed to model robot navigation where the places of navigating agents can change among nodes. The metric dimension m d ( G ) of a graph G is the smallest number k for which G contains a vertex set W , such that | W | = k and every pair of vertices of G possess different distances to at least one vertex in W ...

Mufti, Z Nadeem, M Ahmad, Ali Ahmad, Z

Let G = (V, E) be a connected graph, let x ∈ V (G) be a vertex and e = yz ∈ E(G) be an edge. The distance between the vertex x and the edge e is given by d G (x, e) = min{d G (x, y), d G (x, z)}. A vertex t ∈ V (G) distinguishes two edges e, f ∈ E(G) if d G (t, e) = d G (t, f). A set R ⊆ V (G) is an edge metric generator for G if every two edges of...

imran, shahid siddiqui, muhammad kamran imran, muhammad hussain, muhammad

Let G = (V, E) be a connected graph and d(x, y) be the distance between the vertices x and y in G. A set of vertices W resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in W. A metric dimension of G is the minimum cardinality of a resolving set of G and is denoted by dim(G). In this paper, Cycle, P...

Bensmail, Julien Mazauric, Dorian Mc Inerney, Fionn Nisse, Nicolas Pérennes, Stéphane

Seager introduced the following game in 2013. An invisible and immobile target is hidden at some vertex of a graph $G$. Every step, one vertex $v$ of $G$ can be probed which results in the knowledge of the distance between $v$ and the target. The objective of the game is to minimize the number of steps needed to locate the target, wherever it is. W...

hussain, zafar munir, mobeen chaudhary, maqbool kang, shin min

Concepts of resolving set and metric basis has enjoyed a lot of success because of multi-purpose applications both in computer and mathematical sciences. For a connected graph G(V,E) a subset W of V(G) is a resolving set for G if every two vertices of G have distinct representations with respect to W. A resolving set of minimum cardinality is calle...

Zemljič, Sara Sabrina

In this thesis we study the metric properties of Sierpiński graphs. Sierpiński graphs form a two-parametric family of graphs similar to Hanoi graphs that originate in the Tower of Hanoi puzzle. Sierpiński graphs can be found in various areas of mathematics and elsewhere. First we introduce the family of Sierpiński graphs and their variants. These f...

Poklukar, Nina

Gravier, Sylvain Parreau, Aline Rottey, Sara Storme, Leo Vandomme, Elise

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and 2ln(|V|)+1 where V is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known e...

Gravier, Sylvain Parreau, Aline Rottey, Sara Storme, Leo Vandomme, Élise

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and 2ln(vertical bar V vertical bar) + 1 where V is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional s...