Tree endomorphism and distance of uncovered vertices

60 Views Asked by At

$\newcommand{\diam}{\operatorname{diam}}$ Let $T$ be a tree. $f$ is an endomorphism of $T$, if $uv$ is an edge in $T$, then either $f(u)f(v)$ is an edge in $T$ or $f(u)=f(v)$.

$d_T(x,y)$ is the length (# of edges) of the unique $xy$-path in $T$. Let $d_T(X,Y) = \max_{x\in X} \min_{y\in Y} d_T(x,y)$ and $\diam_T(X) = \max_{x,y\in X} d_T(x,y)$.

Conjecture: Let $T=(V,E)$ be a tree, $f:V\to V$ is an endomorphism of $T$. $U=f(V)$. Let $P$ be a path of $k$ nodes and is a subgraph of $T$. If $f(P)$ consists of $j$ nodes, then either $\diam_T(\bar{U})\geq k-1$, or $d_T(\bar{U},U)\geq k-j$.

This conjecture is true when the tree is a path. I wonder does it work in general.

1

There are 1 best solutions below

8
On BEST ANSWER

After trying a constructive proof, I've found a counterexample. Consider the following tree $T$ Tree For this tree, a maximum length path is from $1$ to $8$ and has a length of $7$ edges. Then let $$f(9)=1$$ $$f(10)=2$$ $$f(n)=3$$ for all other values of $n$. Then $U=f(T)$ is exactly the linear graph $$U=(1,2,3)$$ It is clear that $$k=|P|=7$$ $$j=|f(P)|=0$$ $$\textrm{diam}_T(\overline{U})=4<k-1=6$$ $$d_T(\overline{U},U)=5<k-j=7$$ The reason the proof fails is because $f(P)$ is not necessarily of the same length of the longest path between a point in $U$ to a point in $U$ which is adjacent to $\overline{U}$.