Connectivity of some Algebraically Defined Digraphs

Abstract

Let $p$ be a prime, $e$ a positive integer, $q=p^e$, and let ${\mathbb{F}}_q$ denote the finite field of $q$ elements. Let $f_i:{\mathbb{F}}_q^2\to {\mathbb{F}}_q$ be arbitrary functions, where $1\le i\le l$, $i$ and $l$ are integers. The digraph $D=D(q;\mathbf{f})$, where $\mathbf{f}=(f_1,\dots ,f_l):{\mathbb{F}}_q^2\to {\mathbb{F}}_q^l$, is defined as follows. The vertex set of $D$ is ${\mathbb{F}}_q^{l+1}$. There is an arc from a vertex $\mathbf{x}=(x_1,\dots ,x_{l+1})$ to a vertex $\mathbf{y}=(y_1,\dots ,y_{l+1})$ if $x_i+y_i=f_{i-1}(x_1,y_1)$ for all $i$, $2\le i\le l+1$. In this paper we study the strong connectivity of $D$ and completely describe its strong components. The digraphs $D$ are directed analogues of some algebraically defined graphs, which have been studied extensively and have many applications.

11 pages