Bi-Metric Dimension of Graphs

NEW

Problem: For finite simple connected graphs $G$, let $\beta(G)$ be the usual metric dimension. Let $\delta(u,v)$ denote the length of a longest simple $u$-$v$ path, with $\delta(u,u)=0$. A set $S=\{s_1,\dots,s_k\}\subseteq V(G)$ is bi-resolving if every vertex $x$ is uniquely determined by

Let $\beta_b(G)$ be the minimum size of a bi-resolving set. The problem asks whether there is a least positive integer $k$ such that

for every graph $G$.

This is the natural formalization from the paper title and notation: $\beta$ is standard metric dimension, and $\beta_b$ is the bi-metric dimension using shortest and longest path distances.

Result: No such integer exists. The difference $\beta(G)-\beta_b(G)$ is unbounded.

For $t\ge2$, construct $G_t$ as follows. Start with a path $a_1a_2\cdots a_t$. Attach two leaves $x_i,y_i$ to each $a_i$. Add a new vertex $r$ adjacent to every other vertex. Thus

The pairs $\{x_i,y_i\}$ are false twins, since

Hence every metric or bi-metric resolving set must contain at least one vertex from each pair $\{x_i,y_i\}$. Therefore

Let $S=\{x_1,\dots,x_t\}$. Distances to $S$ distinguish all vertices except possibly the $y_i$’s: each $x_i$ has a $0$ in coordinate $i$, each $a_i$ has a $1$ in coordinate $i$, $r$ has all coordinates $1$, and every $y_i$ has all distance coordinates $2$.

The detour distances distinguish the $y_i$’s. Indeed, for fixed $i$, writing

one has

while for $k\ne i$,

The first equality follows because any longest $y_i$-$x_i$ path using $r$ can extend through the underlying tree on only one side of $a_i$, while a path to a farthest leaf realizes length $M_i+4$. The second inequality is realized by routing from $y_k$ through the longer side of the spine, then through $r$, then back to $x_i$; the two spine portions are disjoint, giving one more edge than the sibling case. Thus $S$ is bi-resolving, so

Now compute $\beta(G_t)$. Since one vertex from each false-twin pair is necessary, suppose a resolving set contains exactly one from $m$ of the pairs. The unchosen vertices from those $m$ pairs all have equal distance $2$ to every chosen twin vertex and equal distance $1$ to $r$. A support vertex $a_i$ distinguishes only the unchosen vertex from its own pair. Hence, among those $m$ unchosen vertices, at least $m-1$ corresponding support vertices are additionally necessary. This gives

Conversely,

is a metric resolving set: the $x_i$’s distinguish all $x_i,a_i,r$, and the added $a_1,\dots,a_{t-1}$ distinguish $y_1,\dots,y_t$. Therefore

Thus

which is unbounded as $t\to\infty$. Therefore no positive integer $k$ satisfies the proposed universal bound.

Citation: No known prior resolution is used here. The notation and problem come from A. Raghavendra, B. Sooryanarayana, and Chandru Hegde, “Bi-Metric Dimension of Graphs,” 2014, DOI: 10.9734/BJMCS/2014/10491.