Contents Online

# Journal of Combinatorics

## Volume 11 (2020)

### Number 2

### Enumerating cliques in direct product graphs

Pages: 351 – 358

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n2.a6

#### Author

#### 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, \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.

Received 18 July 2017

Published 14 January 2020