Almost Regular Robust Graphs for Arbitrary Number of Nodes

Regular graphs play an important role in designing interconnection networks for multiprocessing systems; but these regular graphs like hypercubes or star graphs cannot be constructed with an arbitrary number of nodes. The purpose of the present paper is to examine two families of almost regular maximally fault tolerant graphs (based on hypercubes and star graphs respectively) that can be defined for an arbitrary number of nodes.