Enumerating Cliques in Direct Product Graphs

Abstract

The unitary Cayley graph of $\mathbb Z/n\mathbb Z$, denoted $G_{\mathbb Z/n\mathbb Z}$, is the graph with vertices $0,1,\ldots,$ $n-1$ in which two vertices are adjacent if and only if their difference is relatively prime to $n$. These graphs are central to the study of graph representations modulo integers, which were originally introduced by Erdős and Evans. We give a brief account of some results concerning these beautiful graphs and provide a short proof of a simple formula for the number of cliques of any order $m$ in the unitary Cayley graph $G_{\mathbb Z/n\mathbb Z}$. This formula involves an exciting class of arithmetic functions known as Schemmel totient functions, which we also briefly discuss. More generally, the proof yields a formula for the number of cliques of order $m$ in a direct product of balanced complete multipartite graphs.

5 pages, 1 figure