0
$\begingroup$

I am unable to understand Lemma 2.3 of

  • Carmen Hernando, Mercè Mora, Ignacio M. Pelayo, Carlos Seara, David R. Wood, Extremal Graph Theory for Metric Dimension and Diameter, Electronic J. Combinatorics 17 (2010) #R30, doi:10.37236/302, arXiv:0705.0938.

It says that if $u, v$ are twins in a connected graph $G$, then $dist(u, x) = dist(v, x)$ for every vertex $x\in V(G)\setminus \{u, v\}$.

I tried like this: Suppose that $x\in V(G)\setminus \{u, v\}$. Let $P$ be the shortest path from $x$ to $u$. We need to show that $P$ is also the shortest path from $x$ to $v$.

How can we show that? Can someone please elaborate the issue?

$\endgroup$
1
  • $\begingroup$ Lemma 2.3 is immediate from the definition given on the line immediately above (which is why its proof is omitted). Your idea does not work, as $P$ need not even be a path from $x$ to $v$ (under the definition of "path" used in the cited paper). You already got an answer, but for future reference (or if the given answer is not sufficient), the correct forum for this question is math.stackexchange.com. $\endgroup$
    – Ville Salo
    Sep 2, 2020 at 7:06

1 Answer 1

1
$\begingroup$

You can use this: if $u\ne x$, $$dist(u,x)=1+\min\{dist(w,x):uw\in E\}.$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.