Paley-like graphs over finite fields from vector spaces

Abstract

Motivated by the well-known Paley graphs over finite fields and their generalizations, in this paper we explore a natural multiplicative-additive analogue of such graphs arising from vector spaces over finite fields. Namely, if $n\ge 2$ and $U⊊{\mathbb{F}}_{q^n}$ is an ${\mathbb{F}}_q$-vector space, $G_U$ is the (undirected) graph with vertex set $V(G_U)={\mathbb{F}}_{q^n}$ and edge set $E(G_U)=\{(a,b)\in {\mathbb{F}}_{q^n}^2|a\ne b,ab\in U\}$. We describe the structure of an arbitrary maximal clique in $G_U$ and provide bounds on the clique number $\omega (G_U)$ of $G_U$. In particular, we compute the largest possible value of $\omega (G_U)$ for arbitrary $q$ and $n$. Moreover, we obtain the exact value of $\omega (G_U)$ when $U⊊{\mathbb{F}}_{q^n}$ is any ${\mathbb{F}}_q$-vector space of dimension $d_U\in \{1,2,n-1\}$.

Accepted for publication in Finite Fields and Their Applications