Connectivity of consecutive-\(d\) digraphs
type: Item
instance of: scholarly article
title: Connectivity of consecutive-\(d\) digraphs
zbMATH Open document ID: 0776.05045
DOI: 10.1016/0166-218X(92)90131-S
author: G. W. Peck
author: Du Ding-Zhu
author: D. Frank Hsu
published in: Discrete Applied Mathematics
publication date: 1993-01-16T00:00:00Z
review text: A consecutive-\(d\) digraph \(G(d,n,q,r)\) is a digraph with \(n (>d)\) nodes labeled by the residues modulo \(n\) and there exist links from \(i\) to \(j\) iff \(j\equiv qi+r,\dots,qi+r+d-1\pmod n\) for some given \(q\) and \(r\), \(q\neq 0\). This concept generalizes the class of generalized De Bruijn digraphs (see, i.e., \textit{D. Z. Du} and \textit{F. K. Hwang} [Networks 18, No. 1, 27-38 (1988; Zbl 0654.05036)]). The authors prove that if a consecutive-\(d\) digraph is modified by connecting nodes with a loop into a circuit and deleting all loops then the link-connectivity of such a graph is \(d\) \((d>2)\) iff \(\text{gcd}(q,n)\) divides \(d\).
reviewed by: Michael Hager
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 94306
zbMATH Keywords: generalized De Bruijn digraphs
MaRDI profile type: Publication
cites work: The Hamiltonian property of consecutive-\(d\) digraphs
cites work: Generalized de Bruijn digraphs
cites work: Quelques problèmes de connexite dans les graphes orientes
cites work: Connectivity of Imase and Itoh digraphs
cites work: The Hamiltonian property of linear functions
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: Design of a d-connected digraph with a minimum number of edges and a quasiminimal diameter
full work available at URL: 0166-218x(92)90131-s
OpenAlex ID: W2066441664
description: scientific article; zbMATH DE number 94306