ON METRIC DIMENSION OF FUNCTIGRAPHS
Linda Eroh, Cong X. Kang, Eunjeong Yi · Discrete Mathematics Algorithms and Applications · 2013
The metric dimension of a graph G, denoted by dim (G), is the minimum number of vertices such that each vertex is uniquely determined by its distances to the chosen vertices. Let G 1 and G 2 be disjoint copies of a graph G and let f : V(G 1 ) → V(G 2 ) be a function. Then a functigraphC(G, f) = (V, E) has the vertex set V = V(G 1 ) ∪ V(G 2 ) and the edge set E = E(G 1 ) ∪ E(G 2 ) ∪ {uv | v = f(u)}. We study how metric dimension behaves in passing from G to C(G, f) by first showing that 2 ≤ dim (C(G, f)) ≤ 2n - 3, if G is a connected graph of order n ≥ 3 and f is any function. We further investigate the metric dimension of functigraphs on complete graphs and on cycles.