Diameter of some monomial digraphs

DOI10.1142/9789814719261_0010MaRDI QIDQ2829804zbMATH OpenOpenAlexFDO

Authors A. Kodess, Felix Lazebnik, S. Smith, J. Sporre

Publication date 8 November 2016

Published in Contemporary Developments in Finite Fields and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.11360

zbMATH Keywords

diametermonomial digraphstrong connectivity

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Polynomials over finite fields (11T06)

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}omathbb{F}_q$ be arbitrary functions, where $1leilel$, $i$ and $l$ are integers. The digraph $$, where $$, is defined as follows. The vertex set of $D$ is $mathbb{F}_q^{l+1}$. There is an arc from a vertex $$ to a vertex $$ if $x_i+y_i=f_{i-1}(x_1,y_1)$ for all $i$, $2leilel+1$. In this paper we study the diameter of $$ in the special case of monomial digraphs $D(q;m,n)$: $$ and $f_1(x,y)=x^m{y}^n$ for some nonnegative integers $m$ and $n$.

Review text

The paper first defines a monomial digraph, which is directed analogue of some algebraically defined graphs, which have been extensively studied and used in many applications. The questions of strong connectivity of monomial digraphs and descriptions of their components were answered by \textit{A. Kodess} and \textit{F. Lazebnik} [Electron. J. Comb. 22, No. 3, Research Paper P3.27, 11 p. (2015; Zbl 1360.05077)]. Most of the present results are concerned with the determination of the diameter of a component for strong monomial digraphs. Two theorems are given, listing some of their properties.NEWLINENEWLINEFor the entire collection see [Zbl 1345.11003].

Recommendations

• A note on degree/diameter monotonicity of digraphs
• The diameter of almost Eulerian digraphs
• scientific article; zbMATH DE number 1375161
• scientific article; zbMATH DE number 1334620
• The diameters of almost all Cayley digraphs
• scientific article; zbMATH DE number 969185
• Maximum diameter of regular digraphs
• Some properties of graphs of diameters
• The diameter of cyclic Kautz digraphs
• The diameter of cyclic Kautz digraphs

Cited in

(3)

• On monochromatic pairs of nondecreasing diameters
• Classification by girth of three-dimensional algebraically defined monomial graphs over the real numbers
• Computer Algebra in Scientific Computing

This page was built for publication: Diameter of some monomial digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829804)