Enumerating cliques in direct product graphs

The unitary Cayley graph of $\mathbb{Z} / n \mathbb{Z}$, denoted $G_{\mathbb{Z} / n \mathbb{Z}}$, is the graph with vertices $0, 1, \dotsc, 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.

Keywords

unitary Cayley graph, clique, Schemmel totient function, direct product graph, complete multipartite graph

2010 Mathematics Subject Classification

Primary 05C30. Secondary 05C69.

Full Text (PDF format)

Received 18 July 2017

Published 14 January 2020