Cayley Graphs Isomorphic to the Product of Two Cayley Graphs

Abstract

Let \(*\) be a binary graph operation. We call \(*\) a Cayley operation if \(\Gamma_1 * \Gamma_2\) is a Cayley graph for any two Cayley graphs \(\Gamma_1\) and \(\Gamma_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 \(\Gamma_1\) and \(\Gamma_2\), the graph product \(\Gamma_1 * \Gamma_2\) is again a Cayley graph. The latter question is studied for the union, join (sum), replacement, and zig-zag products of graphs.