Pancycles and hamiltonian-connectedness of the hierarchical cubic network

摘要

We show that the hierarchical cubic network, an alternative to the hypercube, is hamiltonian-connected using Gray codes. A network is hamiltonian-connected if it contains a hamiltonian path between every two distinct nodes. In other words, a hamiltonian-connected network can embed a longest linear array between every two distinct nodes with dilation, congestion, load, and expansion equal to one. We also show that the hierarchical cubic network contains cycles of all possible lengths but three and five. Since the hypercube contains cycles only of even lengths, it is concluded that the hierarchical cubic network is superior to the hypercube in hamiltonicity. Our results can be applied to the hierarchical folded-hypercube network as well.