Design of a \(d\)-connected digraph with a minimum number of edges and a quasiminimal diameter. II
type: Item
instance of: scholarly article
title: Design of a \(d\)-connected digraph with a minimum number of edges and a quasiminimal diameter. II
zbMATH Open document ID: 0848.05034
DOI: 10.1016/0166-218X(94)00113-R
author: Terunao Soneoka
author: Makoto Imase
author: Yoshifumi Manabe
published in: Discrete Applied Mathematics
publication date: 1996-07-07T00:00:00Z
review text: Let \(n = md + t\) where \(n \geq 2d \geq 6\) and \(0 \leq t < d\). The authors construct a \(d\)-regular and \(d\)-connected digraph \(G(n,d)\) with \(n\) nodes such that the diameter \(D(G(n,d))\) is at most \(\lceil \log_dm \rceil + \lceil t/d \rceil + 1\). In particular, \(D(G (n,d))\) is at most two more than a lower bound for the diameter of such a digraph in general, and at most one more then the lower bound when \(n \leq d^3 + d\). This construction covers some cases not covered in earlier papers. For Part I see ibid. 27, No. 3, 255-265 (1990; Zbl 0707.05027).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 897367
zbMATH Keywords: digraph
zbMATH Keywords: diameter
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Large fault-tolerant interconnection networks
cites work: On the impossibility of directed Moore graphs
cites work: Connectivity of consecutive-\(d\) digraphs
cites work: Generalized de Bruijn digraphs
cites work: Line Digraph Iterations and the (d, k) Digraph Problem
cites work: Design to Minimize Diameter on Building-Block Network
cites work: A Design for Directed Graphs with Minimum Diameter
cites work: Connectivity of Regular Directed Graphs with Small Diameters
cites work: Q3792704
cites work: An algorithm for construction of ak-connected graph with minimum number of edges and quasiminimal diameter
cites work: A synthesis approach to design optimally fault tolerant network architecture
cites work: Design of a d-connected digraph with a minimum number of edges and a quasiminimal diameter
full work available at URL: 0166-218x(94)00113-r
OpenAlex ID: W4210509512
description: scientific article; zbMATH DE number 897367