Connected Components and Non-bipartiteness of Generalized Paley Graphs

Abstract

In this work, we consider the class of Cayley graphs known as generalized Paley graphs (GP-graphs for short) given by Γ(k, q) = Cay(Fq, {xk : x ∈ F∗ q }), where Fq is a finite field with q elements, both in the directed and undirected case. Hence q = pm with p prime, m ∈ N and one can assume that k | q − 1. We first give the connected components of an arbitrary GP-graph. We show that these components are smaller GP-graphs all isomorphic to each other (generalizing Lim and Praeger’s result from 2009 to the directed case). We then characterize those GPgraphs which are disjoint unions of odd cycles. Finally, we show that Γ(k, q) is non-bipartite except for the graphs Γ(2m−1, 2m), m ∈ N, which are isomorphic to K2 ··· K2, the disjoint union of 2m−1 copies of K2.