Wirelength of 1-fault hamiltonian graphs into wheels and fans

In this paper we obtain a fundamental result to find the exact wirelength of 1-fault hamiltonian graphs into wheels and fans. Using this result we compute the exact wirelength of circulant graphs, generalized Petersen graphs, augmented cubes, crossed cubes, Mőbius cubes, locally twisted cubes, twisted cubes, twisted n-cubes, generalized twisted cubes, hierarchical cubic networks, alternating group graphs, arrangement graphs and tori into wheels and fans. In addition, we find the exact wirelength of hypercubes, folded hypercubes, shuffle cubes, cube connected cycles, cyclic-cubes, wrapped butterfly networks and star graphs into fans.

► A new technique has been evolved to compute the exact wirelength of embeddings. ► We give algorithms to find the exact wirelength of 1-fault hamiltonian graphs into wheels and fans. ► Our algorithms produce exact wirelengths in linear time and cover a wide range of interconnection networks.