Paper detail

Cliques of orders three and four in the Paley-type graphs

Let $n=2^s p_{1}^{α_{1}}\cdots p_{k}^{α_{k}}$, where $s=0$ or $1$, $α_i\geq 1$, and the distinct primes $p_i$ satisfy $p_i\equiv 1\pmod{4}$ for all $i=1, \ldots, k$. Let $\mathbb{Z}_n^\ast$ denote the group of units in the commutative ring $\mathbb{Z}_n$. Recently, we defined a Paley-type graph $G_n$ of order $n$ as the graph whose vertex set is $\mathbb{Z}_n$ and $xy$ is an edge if $x-y\equiv a^2\pmod n$ for some $a\in\mathbb{Z}_n^\ast$. The Paley-type graph $G_n$ resembles the classical Paley graph in a number of ways, and adds to the list of generalizations of the Paley graph. Computing the number of cliques of a particular order in a Paley graph or its generalizations has been of considerable interest. For primes $p\equiv 1\pmod 4$ and $α\geq 1$, by evaluating certain character sums, we found the number of cliques of order $3$ in $G_{p^α}$ and expressed the number of cliques of order $4$ in $G_{p^α}$ in terms of Jacobi sums. In this article we give combinatorial proofs and find the number of cliques of orders $3$ and $4$ in $G_n$ for all $n$ for which the graph is defined.