Optimal fault-tolerant linear arrays

摘要

This paper proves that for every positive integers n and k, there exists a graph G with n + O(k) vertices and maximum degree 3, such that even after removing any k vertices from G, the remaining graph still contains a path of length n-1. This partially settles a problem raised by Zhang 14,15 in connection with the design of fault-tolerant linear arrays.