A note on the partition dimension of Cartesian product graphs

Publication date 20 December 2010

Abstract: Let

G = (V, E)

be a connected graph. The distance between two vertices

u, v i n V

, denoted by

d (u, v)

, is the length of a shortest

u - v

path in

G

. The distance between a vertex

v i n V

and a subset

P s u b s e t V

is defined as

m i n d (v, x) : x i n P

, and it is denoted by

d (v, P)

. An ordered partition

P_{1}, P_{2}, ..., P_{t}

of vertices of a graph

G

, is a emph{resolving partition}of

G

, if all the distance vectors

(d (v, P_{1}), d (v, P_{2}), ..., d (v, P_{t}))

are different. The emph{partition dimension} of

G

, denoted by

p d (G)

, is the minimum number of sets in any resolving partition of

G

. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs

G, H

,

p d (G i m e s H) l e p d (G) + p d (H)

and

p d (G i m e s H) l e p d (G) + d i m (H) .

Consequently, we show that

p d (G i m e s H) l e d i m (G) + d i m (H) + 1.

Recommendations

Cites work

Cited in

(27)

This page was built for publication: A note on the partition dimension of Cartesian product graphs