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 $\hat{I}“(k,q)=Cay({\mathbb{F}}_q,\{x^k:x\in {\mathbb{F}}_q^{\ast }\})$, where ${\mathbb{F}}_q$ is a finite field with $q$ elements, both in the directed and undirected case. Hence $q=p^m$ with $p$ prime, $m\in \mathbb{N}$ and one can assume that $k\mid 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 a Lim and Praeger's result from 2009 to the directed case). We then characterize those GP-graphs which are disjoint unions of odd cycles. Finally, we show that $\hat{I}“(k,q)$ is non-bipartite except for the graphs $\hat{I}“(2^m-1,2^m)$, $m\in \mathbb{N}$, which are isomorphic to $K_2\bigsqcup \cdots \bigsqcup K_2$, the disjoint union of $2^{m-1}$ copies of $K_2$.

22 pages, 3 figures. In Section 4 we use only graph theory and elemetary methods (we don't need to use Artin-Schreier curves anymore)