Computing Metric Dimension of Power of Total Graph

Abstract

For a connected graph $\mathcal {G}$ , the distance $d(u, v)$ between any two vertices $u$ , $v~\in ~\mathcal {V(G)}$ is defined as; $d(u,v)=\min _{\mathcal {P}_{u,v}}\{\text {length of}~\mathcal {P}_{uv}\}$ i.e the minimum length of path connecting any two vertices. Two vertices $u$ , $v$ of a graph $G$ are said to be resolved by a vertices $\mathcal {W}$ of a graph $\mathcal {G}$ if $d(u,w) \neq d(v,w)$ . An ordered set $\mathcal {W} = \{w_{1},w_{2},w_{3},\ldots,w_{k}\}\,\,\in \,\,V(G)$ is resolving set for a connected graph $G$ , if for any two vertices $u$ , $v$ there exists $w_{i} \in W$ such that $d(u,w_{i}) \neq d(v, w_{i})$ . The representation of vertices $v$ w.r.t $\mathcal {W}$ is represented by $r(v|\mathcal {W})$ which is $k$ -vector( $k$ -tuple) $(d(v,w_{1}),d(v,w_{2}),d(v,w_{3}),\ldots,d(v,w_{k}))$ . If the representation of all the vertices of graph $\mathcal {G}$ are different w.r.t $\mathcal {W}$ then $\mathcal {W}$ is the resolving set for $G$ [1]. A resolving set that contains minimum numbers of vertices is metric basis for $\mathcal {G}$ . The cardinality of smallest resolving set is the metric dimension of $\mathcal {G}$ , represented by $dim(\mathcal {G})$ [2], [3]. A family of connected graph $\mathcal {G}$ has unbounded metric dimension if $dim(\mathcal {G})$ depends on order of a graph. In this paper, we show that total graph of path power three and four have unbounded metric dimension. We also proved some results on edges of power of path graph.

Keywords

• Metric Dimension
• basis
• resolving set
• planar graph
• convex polytopes