Strong resolving partitions for strong product graphs and Cartesian product graphs

详细信息查看全文

文摘

A set W

W

of vertices of a connected graph G

G

strongly resolves two different vertices x,y∉W

x, y \notin W

if either d_G(x,W)=d_G(x,y)+d_G(y,W)

d_{G} (x, W) = d_{G} (x, y) + d_{G} (y, W)

or d_G(y,W)=d_G(y,x)+d_G(x,W)

d_{G} (y, W) = d_{G} (y, x) + d_{G} (x, W)

, where

d_{G} (x, W) = min {d_{G} (x, w) : w \in W}

and d_G(x,w)

d_{G} (x, w)

is the length of a shortest x−w

x - w

path. An ordered vertex partition Π={U₁,U₂,…,U_k}

Π = {U_{1}, U_{2}, \dots, U_{k}}

of G

G

is a strong resolving partition for G

G

, if every two different vertices belonging to the same set of the partition are strongly resolved by some set of Π

Π

. The minimum cardinality of a strong resolving partition for G

G

is the strong partition dimension of G

G

. In this article we study the strong resolving partitions and the strong partition dimension of strong product graphs and Cartesian product graphs.

地址：北京市海淀区学院路29号邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700