July 12, 2012: we found an other addition to the literature and
see that our fixed point theorem generalizes the Nowakowski-Rival fixed edge
theorem [1] which can be formulated as follows:
Theorem (Nowakowski-Rival, 1979) A graph endomorphism of a simple connected graph
with no loops has either a fixed edge or vertex.
Nowakowski-Rival formulate this as an fixed edge theorem in that at every
point a loop is added (making the edge relation reflexive).
In that case there is a fixed edge. The theorem is a consequence of our
theorem in the case of trees which is contractible. It is a special case
of the discrete Brouwer. Espianolaa-Kirkb have generalized the theorem
in 2006 to a commutative family of such maps. [2]
[1] R. Nowakowski, I. Rival, Fixed-edge theorem for graphs with loops,
J. Graph Theory, 3,1979, pp 339-350
[2] R. Espínolaa, W.A. Kirkb, Fixedpoint theorems in R-trees with
applications to graph theory
Topology and its Applications, 153(7), 2006, pp 1046-1055