Paley-type graphs of order a product of two distinct primes

Abstract

In this paper, we initiate the study of Paley-type graphs \(\Gamma_N\) modulo \(N=pq\), where \(p,q\) are distinct primes of the form \(4k+1\). It is shown that \(\Gamma_N\) is an edge-regular, symmetric, Eulerian and Hamiltonian graph. Also, the vertex connectivity, edge connectivity, diameter and girth of \(\Gamma_N\) are studied and their relationship with the forms of \(p\) and \(q\) are discussed. Moreover, we specify the forms of primes for which \(\Gamma_N\) is triangulated or triangle-free and provide some bounds (exact values in some particular cases) for the order of the automorphism group \(\operatorname{Aut}(\Gamma_N)\) of the graph \(\Gamma_N\), the chromatic number, the independence number, and the domination number of \(\Gamma_N\).