The Hamiltonian property of linear functions
type: Item
instance of: scholarly article
title: The Hamiltonian property of linear functions
zbMATH Open document ID: 0615.05033
DOI: 10.1016/0167-6377(87)90024-1
published in: Operations Research Letters
publication date: 1987-01-01T00:00:00Z
review text: Consider a digraph G(n,q,r) with n nodes and n links \(i\to qi+r\), \(i=0,1,...,n-1\), where q and r are given. The topologies of many computer networks use G(n,q,r) as basic building block. A digraph is called Hamiltonian if it contains a circuit spanning all nodes. The Hamiltonian property of a network topology provides the capability of configuring the interconnection network as a linear array, which is the configuration with the broadest practical significance, of either n-1 or n nodes in the presence of a single faulty node or link. In this paper we give necessary and sufficient conditions for G(n,q,r) to be Hamiltonian.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 3995716
zbMATH Keywords: Hamiltonian circuit
zbMATH Keywords: circulant digraph
zbMATH Keywords: de Bruijn digraph
zbMATH Keywords: reconfigurable network
zbMATH Keywords: network topology
author: Frank K. Hwang
MaRDI profile type: Publication
full work available at URL: 0167-6377(87)90024-1
OpenAlex ID: W2064612698
cites work: Circulants and their connectivities
cites work: Generalized de Bruijn digraphs
cites work: The Hamiltonian property of generalized de Bruijn digraphs
cites work: Fault-Tolerant Routing in DeBruijn Comrnunication Networks
cites work: THE MAXIMUM CONNECTIVITY OF A GRAPH
cites work: Double loop networks with minimum delay
cites work: Design to Minimize Diameter on Building-Block Network
cites work: A Design for Directed Graphs with Minimum Diameter
cites work: Connectivity of circulant digraphs
description: scientific article; zbMATH DE number 3995716