Minimum weight resolving sets of grid graphs

Publication date 16 September 2016

Abstract: For a simple graph

G = (V, E)

and for a pair of vertices

u, v i n V

, we say that a vertex

w i n V

resolves

u

and

v

if the shortest path from

w

to

u

is of a different length than the shortest path from

w

to

v

. A set of vertices

R s u b s e t e q V

is a resolving set if for every pair of vertices

u

and

v

in

G

, there exists a vertex

w i n R

that resolves

u

and

v

. The minimum weight resolving set problem is to find a resolving set

M

for a weighted graph

G

such that

s u m_{v i n M} w (v)

is minimum, where

w (v)

is the weight of vertex

v

. In this paper, we explore the possible solutions of this problem for grid graphs

P_{n} s q u a r e P_{m}

where

3 l e q n l e q m

. We give a complete characterisation of solutions whose cardinalities are 2 or 3, and show that the maximum cardinality of a solution is

2 n - 2

. We also provide a characterisation of a class of minimals whose cardinalities range from

4

to

2 n - 2

.

Recommendations

Cites work

Cited in

(5)

Describes a project that uses

Uses Software

This page was built for publication: Minimum weight resolving sets of grid graphs