Tree equidistant dimension conjecture

1. Definitions and the conjecture

Let $G$ be a connected graph. A set $S\subseteq V(G)$ is a distance-equalizer set if, for every two distinct vertices $x,y\in V(G)\setminus S$, there is a vertex $w\in S$ such that

$$d_G(x,w)=d_G(y,w).$$

The equidistant dimension $\operatorname{eqdim}(G)$ is the minimum cardinality of a distance-equalizer set of $G$.

The conjecture states that every tree $T$ of order $n$ satisfies

$$\operatorname{eqdim}(T)\leq \operatorname{eqdim}(P_n).$$

We show that this already fails for $n=9$.

2. The counterexample

Let $T$ be the 9-vertex spider whose three arms have lengths $4,3,1$:

a4 -- a3 -- a2 -- a1 -- c -- b1 -- b2 -- b3
                        |
                        d

Equivalently,

$$\begin{aligned} V(T)&=\{c,a_1,a_2,a_3,a_4,b_1,b_2,b_3,d\},\\ E(T)&=\{ca_1,a_1a_2,a_2a_3,a_3a_4, cb_1,b_1b_2,b_2b_3,cd\}. \end{aligned}$$

We will prove

$$\boxed{\operatorname{eqdim}(T)=6>5=\operatorname{eqdim}(P_9)}.$$

3. Two elementary observations

Parity observation. If $G$ is bipartite and $x,y$ lie in opposite bipartition classes, then

$$d_G(x,w)\not=d_G(y,w)$$

for every vertex $w$: one of the two distances is even and the other is odd. Consequently, the complement of every distance-equalizer set in a bipartite graph must lie entirely in one bipartition class.

Unique-midpoint observation. Let $u,v$ be distinct vertices of a tree at even distance, let $m$ be the midpoint of the $u$-$v$ path, and suppose $m$ has degree $2$. Then $m$ is the only vertex equidistant from $u$ and $v$.

Indeed, for any vertex $w$, let $z$ be the median of $u,v,w$, that is, the unique common vertex of the three paths joining these vertices pairwise. Then

$$d(w,u)=d(w,z)+d(z,u),\qquad d(w,v)=d(w,z)+d(z,v).$$

Thus $d(w,u)=d(w,v)$ implies $d(z,u)=d(z,v)$, and hence $z=m$. If $w\ne m$, the path from $m$ to $w$ would then have to leave the $u$-$v$ path through an additional edge incident with $m$. But the two edges incident with $m$ are already the two path edges, since $\deg(m)=2$. Therefore $w=m$.

4. Exact computation of $\operatorname{eqdim}(T)$

Upper bound

Consider

$$S_0=\{a_1,a_3,a_4,b_1,b_3,d\}.$$

Its complement is $\{c,a_2,b_2\}$. The following vertices of $S_0$ equalize the three pairs in the complement:

Pair	Witness in $S_0$	Common distance
$c,a_2$	$a_1$	$1$
$c,b_2$	$b_1$	$1$
$a_2,b_2$	$d$	$3$

Thus $S_0$ is a distance-equalizer set and

$$\operatorname{eqdim}(T)\leq 6.$$

Lower bound

The bipartition classes of $T$ are

$$X=\{c,a_2,a_4,b_2\},\qquad Y=\{a_1,a_3,b_1,b_3,d\}.$$

Suppose, for a contradiction, that $S$ is a distance-equalizer set with $|S|\leq5$, and put $R=V(T)\setminus S$. Then $|R|\geq4$. By the parity observation, either $R\subseteq X$ or $R\subseteq Y$.

Since $|X|=4$ and $|Y|=5$, if $R\subseteq X$, then $R=X$; if $R\subseteq Y$, then any four vertices of $R$ form one of the five four-subsets of $Y$. Thus $R$ must contain one of the six four-sets $R_0$ in the following table. Each row also gives two vertices of $R_0$ and their unique equidistant vertex.

Four-set $R_0\subseteq R$	Pair in $R_0$	Unique equidistant vertex
$X$	$c,a_4$	$a_2$
$Y\setminus\{a_1\}$	$b_3,d$	$b_1$
$Y\setminus\{a_3\}$	$a_1,b_3$	$b_1$
$Y\setminus\{b_1\}$	$a_3,d$	$a_1$
$Y\setminus\{b_3\}$	$a_3,b_1$	$a_1$
$Y\setminus\{d\}$	$a_1,b_3$	$b_1$

In every row, the displayed pair is at distance $4$, its displayed midpoint has degree $2$, and that midpoint belongs to $R_0\subseteq R$. The unique-midpoint observation therefore shows that no vertex of $S$ can equalize the displayed pair. This contradicts the definition of a distance-equalizer set.

Hence no distance-equalizer set has size at most $5$, so

$$\operatorname{eqdim}(T)\geq6.$$

Together with the upper bound, this proves

$$\operatorname{eqdim}(T)=6.$$

5. Exact computation of $\operatorname{eqdim}(P_9)$

Label the path $P_9$ as

$$p_0-p_1-p_2-p_3-p_4-p_5-p_6-p_7-p_8.$$

The set

$$S_P=\{p_1,p_3,p_4,p_5,p_7\}$$

is a distance-equalizer set. Its complement is $\{p_0,p_2,p_6,p_8\}$, and the midpoints of its six pairs are as follows:

Pair	Midpoint in $S_P$
$p_0,p_2$	$p_1$
$p_0,p_6$	$p_3$
$p_0,p_8$	$p_4$
$p_2,p_6$	$p_4$
$p_2,p_8$	$p_5$
$p_6,p_8$	$p_7$

Therefore $\operatorname{eqdim}(P_9)\leq5$.

Conversely, suppose that $P_9$ has a distance-equalizer set $S$ with $|S|\leq4$. Its complement $R$ has at least five vertices and, by the parity observation, must lie in one bipartition class. The two classes have sizes five and four, so necessarily

$$R=\{p_0,p_2,p_4,p_6,p_8\}.$$

But the only vertex equidistant from $p_0$ and $p_8$ is their midpoint $p_4$, which lies in $R$, not in $S$. This is a contradiction. Thus $\operatorname{eqdim}(P_9)\geq5$, and hence

$$\operatorname{eqdim}(P_9)=5.$$

It follows that

$$\operatorname{eqdim}(T)=6>5=\operatorname{eqdim}(P_9),$$

which disproves MathDB #351395.

6. Additional exhaustive verification

The proof above is entirely independent of computation. As a separate check, all-pairs graph distances were computed and the defining condition

$$\forall\{x,y\}\subseteq V(G)\setminus S\quad \exists w\in S:\ d(x,w)=d(y,w)$$

was tested directly over vertex subsets.

For the displayed tree, a full scan of all $2^9=512$ subsets gives the following numbers of distance-equalizer sets by cardinality:

| $|S|$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | Number | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 16 | 9 | 1 |

In particular, the minimum size is $6$, and there are exactly nine minimum distance-equalizer sets. The same direct test gives minimum size $5$ for $P_9$.

For an independent minimality check, all trees of orders at most $9$ were generated as follows. For $2\leq n\leq9$, every Prüfer sequence of length $n-2$ was decoded into a labeled tree (with the one-vertex tree handled separately). Each unrooted tree was assigned a canonical code by repeatedly deleting leaves to find its center or two centers and then recursively sorting the rooted branch codes. One representative of each canonical code was kept. For every representative, all vertex subsets were tested directly against the definition of a distance-equalizer set. This gives:

| Order $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | Number of non-isomorphic trees | 1 | 1 | 1 | 2 | 3 | 6 | 11 | 23 | 47 | | $\operatorname{eqdim}(P_n)$ | 0 | 1 | 1 | 2 | 3 | 4 | 4 | 5 | 5 | | Number violating the conjecture | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |

The unique violating isomorphism class at order $9$ is the spider with arm lengths $4,3,1$ displayed above. Thus the computation also identifies it as a smallest-order counterexample. This computational minimality claim is supplementary; the explicit hand proof in Sections 3–5 is already a complete disproof of the conjecture.

Reference

A. González, C. Hernando, and M. Mora, “The Equidistant Dimension of Graphs,” Bulletin of the Malaysian Mathematical Sciences Society 45 (2022), 1757–1775. DOI: 10.1007/s40840-022-01295-z; arXiv:2107.10805.