Home » Subject » Graph Theory » Extremal G.T.

Extremal problem on the number of tree endomorphism

Importance: Medium ✭✭
Author(s): Zhicong Lin
Subject: Graph Theory
» Extremal Graph Theory
Keywords:
Recomm. for undergrads: yes
Posted by: shudeshijie
on: March 1st, 2011
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.


* indicates original appearance(s) of problem.
add new comment

it is not open

On November 25th, 2020 Anonymous says:

This problem is not open. Look at this: https://mathscinet.ams.org/mathscinet/search/publdoc.html?r=1&pg1=MR&s1=3284058&loc=fromrevtext

reply

the upper bound is proved

On March 23rd, 2012 Anonymous says:

the upper bound is proved recently.

reply

counterexample

On March 20th, 2011 leshabirukov says:

Asymmetric tree (http://en.wikipedia.org/wiki/Asymmetric_graph, http://upload.wikimedia.org/wikipedia/commons/a/ad/Asymmetric_tree.svg) has single, trivial endomorphism.

Update: Sorry, I have confused endomorphism with automorphism.

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.