### Abstract

For every ε{lunate} > 0 and every integer m > 0, we construct explicitly graphs with O(m/ε{lunate}) vertices and maximum degree O( 1 ε{lunate}^{2}), such that after removing any (1 - ε{lunate}) 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 | Discrete Mathematics |

Volume | 72 |

Issue number | 1-3 |

DOIs | |

State | Published - Dec 1988 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- 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.

*Discrete Mathematics*,*72*(1-3), 15-19. https://doi.org/10.1016/0012-365X(88)90189-6