### Abstract

Using number theoretical tools, we prove two main results for random r-regular circulant graphs with n vertices, when n is sufficiently large and r is fixed. First, for any fixed ε > 0, prime n and L ≥ n ^{1/r} (logn) ^{1+1/r+ε} , walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm to find a vertex bisector and an edge bisector, both of size less than n ^{1-1/r+o(1)}. As circulant graphs are popular network topologies in distributed computing, we show that our results can be exploited for various information dissemination schemes. In particular, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. This settles an open question in an earlier work of the authors (2004) and shows that the generic gossiping algorithms of that work are nearly optimal.

Original language | English |
---|---|

Title of host publication | LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Proceedings |

Editors | David Fernández-Baca |

Place of Publication | Heidelberg |

Publisher | Springer, Springer Nature |

Pages | 542-555 |

Number of pages | 14 |

Volume | 7256 |

ISBN (Print) | 9783642293436 |

DOIs | |

Publication status | Published - 2012 |

Event | 10th Latin American Symposiumon Theoretical Informatics, LATIN 2012 - Arequipa, Peru Duration: 16 Apr 2012 → 20 Apr 2012 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 7256 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 10th Latin American Symposiumon Theoretical Informatics, LATIN 2012 |
---|---|

Country | Peru |

City | Arequipa |

Period | 16/04/12 → 20/04/12 |

## Fingerprint Dive into the research topics of 'Random walks and bisections in random circulant graphs'. Together they form a unique fingerprint.

## Cite this

*LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Proceedings*(Vol. 7256, pp. 542-555). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7256 LNCS). Heidelberg: Springer, Springer Nature. https://doi.org/10.1007/978-3-642-29344-3_46