On the existence of \((d,k)\)-digraphs
type: Item
instance of: scholarly article
title: On the existence of \((d,k)\)-digraphs
zbMATH Open document ID: 0927.05035
DOI: 10.1016/S0012-365X(99)90087-0
author: Joan Gimbert
published in: Discrete Mathematics
publication date: 1999-12-05T00:00:00Z
review text: A \((d,k)\)-digraph \(G\) is a regular digraph of degree \(d\geq 2\), diameter \(k\geq 2\) and order \(d+d^2+\cdots +d^k\) (i.e. one less than the Moore bound). There are several necessary conditions for the existence of such digraphs based on the so-called repeat permutation \(P\); see, e.g., \textit{E. T. Baskoro, M. Miller, J. Plesník}, and \textit{S. Znám} [J. Graph Theory 20, No. 3, 339-349 (1995; Zbl 0838.05054)] and \textit{E. T. Baskoro, M. Miller}, and \textit{J. Plesník} [Graphs Comb. 14, No. 2, 109-119 (1998; Zbl 0905.05033)]. The author derives several relationships between the spectrum of \(G\) and the cycle structure of \(P\) to obtain new necessary conditions. In particular, it is shown that there is exactly one \((4,2)\)-digraph, namely the line digraph of the complete digraph on 5 vertices.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1322024
zbMATH Keywords: digraph
zbMATH Keywords: degree
zbMATH Keywords: diameter
zbMATH Keywords: Moore bound
zbMATH Keywords: spectrum
zbMATH Keywords: almost Moore digraph
reviewed by: Ján Plesník
MaRDI profile type: Publication
cites work: Q4304337
cites work: Digraphs of degree 3 and order close to the moore bound
cites work: Q4552212
cites work: On the structure of digraphs with order close to the Moore bound
cites work: Q4156457
cites work: On the impossibility of directed Moore graphs
cites work: Q4350166
cites work: Line Digraph Iterations and the (d, k) Digraph Problem
cites work: Q5345642
cites work: Q5599324
cites work: Minimum Diameter of Diregular Digraphs of Degree 2
cites work: Q3136996
cites work: Q4001741
cites work: Q4041603
full work available at URL: s0012-365x(99)90087-0
OpenAlex ID: W4210749045
description: scientific article; zbMATH DE number 1322024