On Metric Dimension of Functigraphs

Linda Eroh; Cong X. Kang; Eunjeong Yi

doi:10.1142/S1793830912500607

paper

On Metric Dimension of Functigraphs

arXiv:1111.5864 · doi:10.1142/S1793830912500607

Abstract

The \emph{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}) \to V (G_{2})$ be a function. Then a \emph{functigraph} $C (G, f) = (V, E)$ has the vertex set $V = V (G_{1}) \cup V (G_{2})$ and the edge set $E = E (G_{1}) \cup E (G_{2}) \cup {uv ∣ v = f (u)}$ . We study how metric dimension behaves in passing from $G$ to $C (G, f)$ by first showing that $2 \leq dim (C (G, f)) \leq 2 n - 3$ , if $G$ is a connected graph of order $n \geq 3$ and $f$ is any function. We further investigate the metric dimension of functigraphs on complete graphs and on cycles.

10 pages, 7 figures

On Metric Dimension of Functigraphs

Abstract

Cited by in corpus (2)