The Hamiltonian property of linear functions (Q1820790): Difference between revisions

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.