Connectivity of consecutive-d digraphs

DOI10.1016/0166-218X(92)90131-SMaRDI QIDQ1199422zbMATH OpenOpenAlexFDO

Authors G. W. Peck, Du Ding-Zhu, D. Frank Hsu

Publication date 16 January 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(92)90131-s

zbMATH Keywords

generalized De Bruijn digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40) Applications of graph theory to circuits and networks (94C15)

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\).

Recommendations

• On connectivity of consecutive-d digraphs
• scientific article; zbMATH DE number 828047
• scientific article; zbMATH DE number 1893584
• scientific article; zbMATH DE number 4204369
• Super line-connectivity of consecutive-\(d\) digraphs

Cites work

• A Design for Directed Graphs with Minimum Diameter
• Connectivity of Imase and Itoh digraphs
• Connectivity of Regular Directed Graphs with Small Diameters
• Design of a d-connected digraph with a minimum number of edges and a quasiminimal diameter
• Design to Minimize Diameter on Building-Block Network
• Generalized de Bruijn digraphs
• scientific article; zbMATH DE number 4057536 (Why is no real title available?)
• Quelques problèmes de connexite dans les graphes orientes
• The Hamiltonian property of consecutive-\(d\) digraphs
• The Hamiltonian property of linear functions

Cited in

(12)

• The Hamiltonian property of consecutive-\(d\) digraphs
• On the \(l\)-connectivity of a digraph
• Super line-connectivity of consecutive-\(d\) digraphs
• On connectivity of consecutive-d digraphs
• Design of a d-connected digraph with a minimum number of edges and a quasiminimal diameter. II
• Miscellaneous digraph classes
• Connectivity of circulant digraphs
• Connectivity of Imase and Itoh digraphs
• Connectedness of digraphs and graphs under constraints on the conditional diameter
• Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields
• scientific article; zbMATH DE number 1893584 (Why is no real title available?)
• scientific article; zbMATH DE number 828047 (Why is no real title available?)

This page was built for publication: Connectivity of consecutive-\(d\) digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199422)