A note on the partition dimension of Cartesian product graphs |
| |
Authors: | Ismael G. Yero |
| |
Affiliation: | Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Pa?¨sos Catalans 26, 43007 Tarragona, Spain |
| |
Abstract: | Let G = (V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P1, P2, … , Pt} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P1), d(v, P2), … , d(v, Pt)) are different. The partition dimension of G, denoted by pd(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, pd(G × H) ? pd(G) + pd(H) and pd(G × H) ? pd(G) + dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H) ? dim(G) + dim(H) + 1. |
| |
Keywords: | Resolving sets Resolving partition Partition dimension Cartesian product |
本文献已被 ScienceDirect 等数据库收录! |
|