On Sharp Bounds on Partition Dimension of Convex Polytopes

Abstract

Let <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega $ </tex-math></inline-formula> be a connected graph and for a given <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$l$ </tex-math></inline-formula> -ordered partition of vertices of a connected graph <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega $ </tex-math></inline-formula> is represented as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\beta =\{\beta _{1},\beta _{2}, {\dots },\beta _{l}\}$ </tex-math></inline-formula> . The representation of a vertex <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mu \in V(\Omega)$ </tex-math></inline-formula> is the vector <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$r(\mu |\beta)=(d(\mu,\beta _{1}),d(\mu,\beta _{2}), {\dots }, d(\mu,\beta _{l}))$ </tex-math></inline-formula> . The partition <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\beta $ </tex-math></inline-formula> is a resolving partition for vertices of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega $ </tex-math></inline-formula> if all vertices of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega $ </tex-math></inline-formula> having the unique representation with respect to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\beta $ </tex-math></inline-formula> . The minimum number of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$l$ </tex-math></inline-formula> in the resolving partition for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega $ </tex-math></inline-formula> is known as the partition dimension of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega $ </tex-math></inline-formula> and represented as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$pd(\Omega)$ </tex-math></inline-formula> . Resolving partition and partition dimension have multipurpose applications in networking, optimization, computer, mastermind games and modeling of chemical structures. The problem of computing constant values of partition dimension is NP-hard so one can find sharp bound for the partition dimension of graph. In this article, we computed the upper bound for the convex polytopes <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {E}_{n},~\mathbb {S}_{n},~\mathbb {T}_{n},~\mathbb {G}_{n},~\mathbb {Q}_{n}$ </tex-math></inline-formula> and flower graph <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$f_{n\times 3}$ </tex-math></inline-formula> .

Topics & Concepts