On normal Cayley graphs and hom-idempotent graphs (Q1272791)

This paper studies the cartesian product of graphs as an operation on classes of homomorphically equivalent graphs. The theory of graph homomorphisms is more in the spirit of coloring theory than of isomophism questions, but for some graphs (called cores) the only homomorphisms are automorphisms, and the authors use the automorphism group of a core graph to create a Cayley graph from an arbitrary graph. One of the main results of this paper is that a graph is ``hom-idempotent'' (homomorphically equivalent to its cartesian product with itself) if and only if it is homomorphically equivalent to a normal Cayley graph (``normal'' meaning that the edges are defined by a normal subset of the group). The authors also characterize ``weakly hom-idempotent'' graphs (a generalization of hom-idempotent) and include some related results and examples.