Cayley graphs isomorphic to the product of two cayley graphs

Abstract

Let ∗ be a binary graph operation. We call ∗ a Cayley operation if γ1 ∗ γ2 is a Cayley graph for any two Cayley graphs γ1 and γ2- In this paper, we prove that the cartesian, (categorical or tensor) direct and lexicographic products are Cayley operations. We also investigate the following question: Under what conditions on a binary graph operation ∗ and Cayley graphs γ1 ∗ γ2, the graph product γ1 ∗ γ2 is again a Cayley graph. The latter question is studied for the union, join (sum), replacement and zig-zag products of graphs.