Explicit construction of linear sized tolerant networks Original Research Article

For every image and every integer image, we construct explicitly graphs with image vertices and maximum degree image, such that after removing any image portion of their vertices or edges, the remaining graph still contains a path of length m. This settles a problem of Rosenberg, which was motivated by the study of fault tolerant linear arrays.