Cliques of Orders Three and Four in the Paley-Type Graphs.

Let n = 2 s p 1 α 1 ⋯ p k α k , where s = 0 or 1, α i ≥ 1 , and the distinct primes p i satisfy p i ≡ 1 (mod 4) for all i = 1 , … , k . Let Z n ∗ denote the group of units in the commutative ring Z n . In a recent paper, we defined the Paley-type graph G n of order n as the graph whose vertex set is Z n and xy is an edge if x - y ≡ a 2 (mod n) for some a ∈ Z n ∗ . Computing the number of cliques of a particular order in a Paley graph or its generalizations has been of considerable interest. In our recent paper, for primes p ≡ 1 (mod 4) and α ≥ 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. [ABSTRACT FROM AUTHOR]