Advertisement
Published in:
2015 | OriginalPaper | Chapter
Metric Dimension for Amalgamations of Graphs
Authors : Rinovia Simanjuntak, Saladin Uttunggadewa, Suhadi Wido Saputro
Published in: Combinatorial Algorithms
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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 arbitrary graphs. We give lower and upper bounds for the dimensions, show that the bounds are tight, and construct infinitely many graphs for each possible value between the bounds.