On some resolving partitions for the lexicographic product of two graphs

ABSTRACT

Given a connected graph $G=(V,E)$, the distance $d(u,v)$ between two vertices $u,v\in V$ is the length of a shortest u−v path in G. The distance $d(v,P)$ between a vertex $v\in V$ and a subset $P\subset V$ is defined as $min\left\{d\right(v,x):x\in P\}$. An ordered partition $\mathrm{\Pi }=\{P_1,P_2,\dots ,P_t\}$ of vertices of G is a resolving partition of G, if for any two different vertices u,v of G there exists $P_i\in \mathrm{\Pi }$ such that $d(u,P_i)\ne d(v,P_i)$. The partition dimension of G is the minimum number of sets in any resolving partition of G. In this article, we study the partition dimension of the lexicographic product of two graphs.

KEYWORDS:

• Resolving partition
• partition dimension
• lexicographic product graphs
• graphs partitioning

2010 AMS SUBJECT CLASSIFICATIONS:

• 05C12
• 05C70
• 05C76

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

I.G. Yero  http://orcid.org/0000-0002-1619-1572