We introduce a class of rooted infinite self-similar graphs containing the well known Fibonacci graph and graphs associated with Pisot numbers. We consider directed random walks on these graphs and study their entropy and their limit measures. We prove that every infinite self-similar graph has a random walk of full entropy and that the limit measures of this random walks are absolutely continuous.