This paper proves that for every positive integers n, k and any positive number e, we can explicitly construct a DAG G with n+O(k~(1+ε)) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n, k and any positive number ε, we can explicitly construct a graph H with n + O(k~(2+ε)) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.
展开▼
