Abstract. Let $\rho $ be a nontrivial reflexive binary relation on a finite set $A$ with $|A|\ge3$. We consider clones on $A$ that consist of functions preserving $\rho $ and contain all unary functions with this property. We prove that if $\rho $ is either transitive or strongly intransitive, or symmetric then there exist $2^{\aleph_0}$ such clones provided $\rho $ is not a linear order. We show that, for a linear order on a three-element set, there are only 7 such clones.

AMS Subject Classification (1991): 08A40, 03B50

Received February 22, 2000, and in revised form August 31, 2000. (Registered under 2796/2009.)