### Abstract

For every ɛ0 and every integer m0, we construct explicitly graphs with O(mɛ vertices and maximum degree O(1ɛ^{2}), such that after removing any (1-ɛ) 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 torerant linear arrays.

Original language | English (US) |
---|---|

Pages (from-to) | 15-19 |

Number of pages | 5 |

Journal | Annals of Discrete Mathematics |

Volume | 38 |

Issue number | C |

DOIs | |

State | Published - Jan 1 1988 |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Explicit Construction of Linear Sized Tolerant Networks'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Chung, F. R. K. (1988). Explicit Construction of Linear Sized Tolerant Networks.

*Annals of Discrete Mathematics*,*38*(C), 15-19. https://doi.org/10.1016/S0167-5060(08)70766-0