Connectivity of some algebraically defined digraphs

Aleksandr Kodess¹ ; Felix Lazebnik²

¹University of Rhode Island
²University of Delaware

The electronic journal of combinatorics, Tome 22 (2015) no. 3

Résumé

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\colon\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;\bf{f})$, where ${\bf f}=f_1,\dotso,f_l)\colon\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 ${\bf x} = (x_1,\dotso,x_{l+1})$ to a vertex ${\bf y} = (y_1,\dotso,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.

Détail

DOI : 10.37236/5052

Classification : 05C25, 05C20
Mots-clés : directed graphs, finite fields, strong connectivity