It seems that any distance-transitive graph satisfies your condition (of course, distance-transitivity is much stronger), and you can find many examples (both finite and infinite) in Peter Cameron's nice paper. (A census of infinite distance-transitive graphs, Discrete Math, 1998) Many of these are not Cayley graphs, it would appear.
Igor Rivin
- 96.4k
- 11
- 153
- 366