Digraphs of degree two which miss the Moore bound by two (Q1841909)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Digraphs of degree two which miss the Moore bound by two |
scientific article |
Statements
Digraphs of degree two which miss the Moore bound by two (English)
0 references
20 April 2001
0 references
Given positive integers \(d\) and \(k\), the order \(n\) of a digraph of out-degree at most \(d\) and diameter at most \(k\) is bounded from above by the Moore bound \(M_{d,k}=1+d+d^2+\cdots +d^k\). As shown by the reviewer and \textit{S. Znám} [Acta Fac. Rer. Nat. Univ. Comenian., Math. 29, 29-34 (1974; Zbl 0291.05106)] the equality holds only if \(d=1\) or \(k=1\). In this paper the nonexistence of digraphs of out-degree 2 and diameter \(k\geq 3\) is shown whenever the defect \(M_{d,k}-n=2.\)
0 references
digraph
0 references
Moore bound
0 references
degree
0 references
diameter
0 references
defect
0 references