## Abstract

The edge isoperimetric problem for a graph

*G*is to determine, for each*n*, the minimum number of edges leaving any set of*n*vertices. In general this problem is NP-hard, but exact solutions are known in some special cases, for example when*G*is the usual integer lattice. We solve the edge isoperimetric problem asymptotically for every Cayley graph on Z*. The near-optimal shapes that we exhibit are zonotopes generated by line segments corresponding to the generators of the Cayley graph.*^{d}Original language | English |
---|---|

Article number | 3555 |

Number of pages | 16 |

Journal | Discrete Analysis |

Volume | 7 |

DOIs | |

Publication status | Published - 20 Apr 2018 |