  We classify all solution triples with Fibonacci components to the equation
$a^2+b^2+c^2=3abc+m,$ for positive $m$. We show that for $m=2$ they are
precisely $(1,F(b),F(b+2))$, with even $b$; for $m=21$, there exist exactly two
Fibonacci solutions $(1,2,8)$ and $(2,2,13)$ and for any other $m$ there exists
at most one Fibonacci solution, which, in case it exists, is always minimal
(i.e. it is a root of a Markoff tree). Moreover, we show that there is an
infinite number of values of $m$ admitting exactly one such solution.
