Extremal problem on the number of tree endomorphism

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A tree here is a finite simple connected graph with no cycles. Let $P_n$ be the path on $n$ vertices and $S_n=K_{1,n-1}$ the star (with $S_1=P_1$). An endomorphism of a graph $T$ is a map $\phi:V(T)\to V(T)$ such that $uv\in E(T)$ implies $\phi(u)\phi(v)\in E(T)$. Write $\operatorname{End}(T)$ for the set of these maps; they need not be bijections.

Statement recorded in the supplied source.

The source conjecture asks whether, for every $n\geq1$ and every $n$-vertex tree $T$,\[ |\operatorname{End}(P_n)|\leq |\operatorname{End}(T)|\leq |\operatorname{End}(S_n)|. \] [S2]

Short English statement

Among all trees with the same number of vertices, are the path and the star respectively the minimum and maximum for the number of edge-preserving self-maps?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3283 (OPG-37305). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Extremal problem on the number of tree endomorphism, node 37305, original problem page. Original question and full discussion. https://www.openproblemgarden.org/op/extremal_problem_on_the_number_of_tree_endomorphism.