Extremal problem on the number of tree endomorphism

Medium ★★ Graph Theory » Extremal Graph Theory accessible to undergrads

Author: Zhicong Lin— posted by shudeshijie on 2011-03-01

Status solved high confidence

The conjecture was proved by Csikvari and Lin in 'Graph homomorphisms between trees' (arXiv:1307.6721, 2013; published in Electronic Journal of Combinatorics, 2014). They establish $|\mathrm{End}(P_n)| \leq |\mathrm{End}(T_n)| \leq |\mathrm{End}(S_n)|$ for every tree $T_n$ on $n$ vertices, where $P_n$ and $S_n$ denote the path and star respectively, confirming that the path minimizes and the star maximizes the number of endomorphisms among trees of fixed order.

Cited literature (1)

proof Graph homomorphisms between trees (2013)

Peter Csikvari, Zhicong Lin · arXiv preprint (later published in Electronic Journal of Combinatorics, 2014) · arXiv:1307.6721

Proves $|\mathrm{End}(P_n)| \leq |\mathrm{End}(T_n)| \leq |\mathrm{End}(S_n)|$ for any tree $T_n$ on $n$ vertices, settling Lin's extremal conjecture on tree endomorphisms in both directions.

Reviewer notes. The arXiv abstract page for 1307.6721 explicitly states the result $|\mathrm{End}(P_m)| \leq |\mathrm{End}(T_m)| \leq |\mathrm{End}(S_m)|$, directly proving the OPG conjecture. The paper is co-authored by the conjecture's original poser Zhicong Lin together with Peter Csikvari. The MIT DSpace mirror returned 403 and the EJC PDF was binary-encoded so could not be parsed by WebFetch, but the arXiv version was successfully verified.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).

Conjecture. An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the $ n $ vertices' trees, the star with $ n $ vertices has the most endomorphisms, while the path with $ n $ vertices has the least endomorphisms.

Bibliography

[BT] Bela Bollobas and Mykhaylo Tyomkyn, Walks and paths in trees, http://arxiv.org/abs/1002.2768.