A unified formulation of Kautz network and generalized hypercube (Q2387372)

The hypercube, the Kautz digraph and their generalizations are desirable methods for the design of interconnection networks, while they perform differently. The hypercube \((Q_n)\) has smaller diameter, wider bisection and strong tolerant ability and reliability while its higher vertex degree restricts the architecture cost. The Kautz digraph \((K(d,n))\) has two independent parameters, its diameter, \(d\), is not restricted by its connectivity and vertex degree, \(n\), but the Kautz digraph has vulnerability in fault-tolerance and larger mean distance. In this paper, the authors unify and generalize the hypercube and the Kautz digraph. A unified point of view is the vector system. A novel class of network topologies known as the divided Kautz network (DKN) is proposed, and the topological properties are investigated. The authors show that the well-known hypercube and the Kautz digraph in fact belong to the same class of graphs represented by DKN. The DKN has the generalized hypercube and the Kautz digraph as its two extremes, so it has intermediate performance and cost. Members in the family inherit properties of both the Kautz digraph and the hypercube to a varying degree, this allows network designers to construct networks with different cost and performance for different purposes. This generalization is different from the generalization proposed by Du and Hwang, based on congruence of integers, and it is also different from the generalized \(p\)-cycles which is the Kronecker product \(C_p\times B(d,n)\), where \(C_p\) is a directed cycle of length \(p\). The connectivity, the diameter vulnerability, faut-tolerance and Hamiltonicity are investigated.