### 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 tolerant linear arrays.

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

Pages (from-to) | 1068-1071 |

Number of pages | 4 |

Journal | Discrete Mathematics |

Volume | 306 |

Issue number | 10-11 |

DOIs | |

State | Published - May 28 2006 |

### 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. (2006). Explicit construction of linear sized tolerant networks.

*Discrete Mathematics*,*306*(10-11), 1068-1071. https://doi.org/10.1016/j.disc.2006.03.025