Metric Dimension of Amalgamation of Regular Graphs

Rinovia Simanjuntak, Danang Tri Murdiansyah

Published 2014-01-21Version 1

A set of vertices $S$ resolves a graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of $G$ is the minimum cardinality of a resolving set of $G$. Let $\{G_1, G_2, \ldots, G_n\}$ be a finite collection of graphs and each $G_i$ has a fixed vertex $v_{0_i}$ or a fixed edge $e_{0_i}$ called a terminal vertex or edge, respectively. The vertex-amalgamation of $G_1, G_2, \ldots, G_n$, denoted by $Vertex-Amal\{G_i;v_{0_i}\}$, is formed by taking all the $G_i$'s and identifying their terminal vertices. Similarly, the edge-amalgamation of $G_1, G_2, \ldots, G_n$, denoted by $Edge-Amal\{G_i;e_{0_i}\}$, is formed by taking all the $G_i$'s and identifying their terminal edges. Here we study the metric dimensions of vertex-amalgamation and edge-amalgamation for finite collection of regular graphs: complete graphs and prisms.