Digraphs of degree two which miss the Moore bound by two
type: Item
instance of: scholarly article
title: Digraphs of degree two which miss the Moore bound by two
zbMATH Open document ID: 0959.05054
DOI: 10.1016/S0012-365X(00)00134-5
author: Mirka Miller
author: Jozef Širáň
published in: Discrete Mathematics
publication date: 2001-04-20T00:00:00Z
review text: 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.\)
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1565945
zbMATH Keywords: digraph
zbMATH Keywords: Moore bound
zbMATH Keywords: degree
zbMATH Keywords: diameter
zbMATH Keywords: defect
MaRDI profile type: Publication
Wikidata QID: Q126819161
description: scientific article; zbMATH DE number 1565945