On Normal Cayley Graphs and Hom-idempotent Graphs

A graphGis said to behom-idempotentif there is a homomorphism fromG2toG, andweakly hom-idempotentif for somen ≥ 1 there is a homomorphism fromGn + 1toGn. We characterize both classes of graphs in terms of a special class of Cayley graphs callednormal Cayley graphs. This allows us to construct, for any integern, a Cayley graphGsuch thatGn + 1→Gn↛Gn − 1, answering a question of Hahn, Hell and Poljak [8]. Also, we show that the Kneser graphs are not weakly hom-idempotent, generalizing a result of Albertson and Collins [1] for the Petersen graph.