Connectivity of some Algebraically Defined Digraphs
| Autor: | Kodess, Alex, Lazebnik, Felix |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Electron J Combin. 22(3) (2015), P3.27, 1--11 |
| Druh dokumentu: | Working Paper |
| Popis: | 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;\bf{f})$, where ${\bf f}=(f_1,\dotso,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 ${\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. Comment: 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|